【题解】LuoGu3469：[POI2008]BLO-Blockade

原题传送门 考虑到割点 如果一个点不是割点，那么答案就是$2(n-1)$ 如果是割点，那么答案是$2(n-1)+割掉后个联通块size之积$

问题是怎么求这个size之积 考虑割点求法，与之类似

tarjan割点同时求size 也不需要知道每个点到底是不是割点 如果一个儿子不能不通过自己到达比自己更浅的祖先，说明这个儿子在自己被割掉后会断开 参与答案统计，不是就不管 最终还要加上会断开的点个数*其余点个数

答案输出时不要忘了加上$(n-1)$，再$\ast 2$

Code：

#include <bits/stdc++.h> #define maxn 500010 #define LL long long using namespace std; struct Edge{ int to, next; }edge[maxn << 1]; int num, head[maxn], dfn[maxn], low[maxn], Index; int size[maxn], n, m; LL ans[maxn]; inline int read(){ int s = 0, w = 1; char c = getchar(); for (; !isdigit(c); c = getchar()) if (c == '-') w = -1; for (; isdigit(c); c = getchar()) s = (s << 1) + (s << 3) + (c ^ 48); return s * w; } void addedge(int x, int y){ edge[++num] = (Edge) { y, head[x] }; head[x] = num; } void tarjan(int u){ dfn[u] = low[u] = ++Index; size[u] = 1; int flag = 0, sum = 0; for (int i = head[u]; i; i = edge[i].next){ int v = edge[i].to; if (!dfn[v]){ tarjan(v); size[u] += size[v], low[u] = min(low[u], low[v]); if (low[v] >= dfn[u]) ans[u] += 1LL * sum * size[v], sum += size[v]; } low[u] = min(low[u], dfn[v]); } ans[u] += 1LL * sum * (n - sum - 1); } int main(){ n = read(), m = read(); for (int i = 1; i <= m; ++i){ int x = read(), y = read(); addedge(x, y); addedge(y, x); } for (int i = 1; i <= n; ++i) if (!dfn[i]) tarjan(i); for (int i = 1; i <= n; ++i) printf("%lld\n", ans[i] * 2 + (n - 1) * 2); return 0; }