const int N = 1e6 + 5;
int n, m, rt = 1;
vector<int> vec[N];
void add(int u, int v) {
vec[u].emplace_back(v);
}
int dfn[N], low[N], siz[N], ans[N], tot;
void Tarjan(int u) {
dfn[u] = low[u] = ++ tot;
siz[u] = 1;
for (auto v : vec[u]) {
if (dfn[v]) {
low[u] = min(low[u], dfn[v]);
continue;
}
Tarjan(v);
siz[u] += siz[v];
low[u] = min(low[u], low[v]);
if (low[v] >= dfn[u]) {
// if(u == 1) cout << v << ' ' << siz[v] * (n - siz[v] - 1) << '\n';
ans[u] += siz[v] * (n - siz[v] - 1);
}
}
ans[u] += n - 1;
}
signed main() {
ios::sync_with_stdio(false);
cin.tie(nullptr), cout.tie(nullptr);
cin >> n >> m;
REP(i, 1, m) {
int a, b;
cin >> a >> b;
add(a, b), add(b, a);
}
Tarjan(1);
REP(i, 1, n) cout << ans[i] * 2 << '\n';
return 0;
}
本题中为什么这样的写法会导致根节点的 ans1 会出错呢,求问/kk。