【题解】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;
}