为什么我判割点的时候像模板题一样写就过不了。
#include <bits/stdc++.h>
using namespace std;
const int N = 100010, M = 500010;
int n, m;
int idx, h[N];
struct Edge {int to, ne;} e[M << 1];
void add(int u, int v) {e[idx] = {v, h[u]}, h[u] = idx ++;}
int dfn[N], low[N], tot, siz[N];
bitset<N> iscut;
long long ans[N];
void tarjan(int u, int fa) {
dfn[u] = low[u] = ++ tot;
siz[u] = 1;
int child = 0, sum = 0;
for (int i = h[u]; ~i; i = e[i].ne) {
int v = e[i].to;
if (v == fa) continue;
if (!dfn[v]) {
++ child;
tarjan(v, u);
siz[u] += siz[v];
low[u] = min(low[u], low[v]);
if (/*!iscut[u] && u != fa &&*/ low[v] >= dfn[u]) {
// 这个地方!!!
iscut[u] = 1;
sum += siz[v];
ans[u] += 1ll * siz[v] * (n - siz[v]);
}
}
else low[u] = min(low[u], dfn[v]);
}
if (iscut[u] || (!iscut[u] && u == fa && child >= 2)) {
iscut[u] = 1;
ans[u] += 1ll * (sum + 1) * (n - (sum + 1)) + n - 1;
}
else ans[u] = n - 1 << 1;
}
int main() {
ios::sync_with_stdio(0), cin.tie(0), cout.tie(0);
memset(h, -1, sizeof h);
cin >> n >> m;
for (int i = 1, u, v; i <= m; i ++) {
cin >> u >> v;
add(u, v), add(v, u);
}
tarjan(1, 1);
for (int i = 1; i <= n; i ++)
cout << ans[i] << '\n';
return 0;
}
为什么上面注释的代码去掉就可以过,我看题解都是这么写的,但都没有说。
我还发现下面这组数据我过不了(就是根是割点的情况):
5 4
1 2
1 3
1 4
1 5
输出:
20
8
8
8
8
我上面代码(加上注释)输出的是:
8
8
8
8
8
不知道哪个地方出了问题。
蒟蒻求解qwq