题目链接：

[POI2008]BLO-Blockade

题目描述：

有 $n$ 个节点的无向图，定义封锁一个点为切断这个点的所有连边。求每个节点被封锁后图内的不连通有序点对个数。

解题思路：

Tarjan。

首先分类讨论一下，封锁一个点有两种情况：

1. 不是割点

   这种情况好搞，从图中显然可以看出只有自己和其他 $n - 1$ 个节点不连通，因为是有序节点，所以答案为 $2 \times (n-1)$

2. 是割点

   这种情况就有意思了。

   我们可以发现，如果点 i 为割点，显然去掉这个点之后整个图会变成几个联通块，如下图：

   这种情况我们也很好发现，把联通块的大小两两相乘可得答案。

   记第 i 个联通块为$s_i$

   但是把联通块大小两两相乘的复杂度为 $O(n^2)$ 不能接受，我们可以在 dfs 时把搜索树子树大小算出来，记为 $siz[i]$

   最后的答案即为：

   $(n - 1 - \sum_{i=1}^{t}siz[s_k])*(1+\sum_{i=1}^{t}siz[s_k])$

代码：

#include <cstdio>
#include <cctype>
#include <algorithm>
using namespace std;
const int N = 100010;
const int M = 500010<<1;
inline int read() {
	int x = 0,f = 1;char v = getchar();
	while (!isdigit(v)) {if (v =='-') f = -1;v = getchar();}
	while (isdigit(v)) {x = x * 10 + v - 48;v = getchar();}
	return x * f;
}
int nxt[M],hd[N],to[M],tot = 1,cnt,dfn[N],low[N],siz[N],n,m;
long long ans[N];
bool cut[N];

inline void adde(int u,int v) {
	to[++tot] = v;nxt[tot] = hd[u];hd[u] = tot;
}

inline void addedge(int u,int v) {
	adde(u,v);adde(v,u);
}

void tarjan(int x) {
	dfn[x] = low[x] = ++cnt;
	siz[x] = 1;
	int flag = 0,sum = 0;
	for (int i = hd[x];i;i = nxt[i]) {
		int v = to[i];
		if (!dfn[v]) {
			tarjan(v);
			low[x] = min(low[x],low[v]);
			siz[x] += siz[v];
			if (low[v] >= dfn[x]) {
				flag++;
				ans[x] += (long long)siz[v]*(n - siz[v]);
				sum += siz[v];
				if (x != 1 || flag > 1) {
					cut[x] = 1;
				}
			}
		}	
		else {
			low[x] = min(low[x],dfn[v]);
		}
	}
	if (cut[x]) {
		ans[x] += (long long)(n - sum - 1) * (sum + 1) + (n - 1);
	}
	else {
		ans[x] = 2*(n-1);
	}
}

int main() {
	n = read(),m = read();
	for (int i = 1;i <= m;++i) {
		int x = read(),y = read();
		if (x == y) {
			continue;
		}
		addedge(x,y);
		
	}
	tarjan(1);
	for (int i = 1;i <= n;++i) {
		printf("%lld\n",ans[i]);
	}
	return 0;
}

参考：

部分思路来自于lyd的《算法竞赛进阶指南》

/*【参考程序】
此题隐含的割点的思想。 
siz[x]表示以x为根的搜索树的大小。 
删掉的点x后，则增加的不连通有序对数量可分为3部分:
统计原则：独立的点集与“外界点集 ”相乘。 
1、若子树y满足dfn[x]<=low[y]（子树y独立），则增加Size[y]* (n - siz[y])
2、点x和外界：1*(n-1)
3、外界 和 x+所有独立搜索树：(n-1-sum)*(sum+1)(sum= ∑(siz[y])，y是独立子树的根节点)
*/
#include <bits/stdc++.h>
using namespace std;
typedef long long LL;
const int N=1e5+10;
vector<pair<int, int>> G[N];
int n, m, tsp, low[N], dfn[N], siz[N];
LL ans[N];
void tarjan(int x, int in_id)
{
	dfn[x] = low[x] = ++tsp; siz[x] = 1; 
	int sum = 0;
    for(auto i : G[x]) if(i.second != in_id)
    {
        int y = i.first, id = i.second;
        if(dfn[y] == 0)
        {
            tarjan(y, id);
            siz[x] += siz[y];
            low[x] = min(low[x], low[y]);
            if(dfn[x] <= low[y])
            {
            	ans[x] += (LL)siz[y] * (n - siz[y]);
            	sum += siz[y];
            }
        }
        else low[x] = min(low[x], dfn[y]);
    }
	ans[x] += n - 1;
    ans[x] += (LL)(n - 1 - sum) * (sum + 1);
}
int main()
{
	scanf("%d%d", &n, &m);
	for(int i=1, x, y; i <= m; i++)
	{
		scanf("%d%d", &x, &y); if(x == y) continue;
		G[x].push_back({y, i});
		G[y].push_back({x, i});
	}
	tsp = 0; memset(dfn, 0, sizeof(dfn)); memset(low, 0, sizeof(low));
    memset(ans, 0, sizeof(ans)); memset(siz, 0, sizeof(siz));
	for(int i=1; i <= n; i++) if(dfn[i] == 0) tarjan(i, 0);
	for(int i=1; i <= n; i++) printf("%lld\n", ans[i]);
	return 0;
}

/*【参考程序】
此题隐含的割点的思想。 
siz[x]表示以x为根的搜索树的大小。 
删掉的点x后，则增加的不连通有序对数量可分为3部分:
统计原则：独立的点集与“外界点集 ”相乘。 
1、若子树y满足dfn[x]<=low[y]（子树y独立），则增加Size[y]* (n - siz[y])
2、点x和外界：1*(n-1)
3、外界 和 x+所有独立搜索树：(n-1-sum)*(sum+1)(sum= ∑(siz[y])，y是独立子树的根节点)
*/
#include <bits/stdc++.h>
using namespace std;
typedef long long LL;
const int N=1e5+10;
vector<int> G[N];
int n, m, tsp, low[N], dfn[N], siz[N];
LL ans[N];
void tarjan(int x, int fa)
{
	dfn[x] = low[x] = ++tsp; siz[x] = 1; 
	int sum = 0;
    for(int y : G[x]) if(y != fa)
    {
        if(dfn[y] == 0)
        {
            tarjan(y, x);
            siz[x] += siz[y];
            low[x] = min(low[x], low[y]);
            if(dfn[x] <= low[y])
            {
            	ans[x] += (LL)siz[y] * (n - siz[y]);
            	sum += siz[y];
            }
        }
        else low[x] = min(low[x], dfn[y]);
    }
	ans[x] += n - 1;
    ans[x] += (LL)(n - 1 - sum) * (sum + 1);
}
int main()
{
	scanf("%d%d", &n, &m);
	for(int i=1, x, y; i <= m; i++)
	{
		scanf("%d%d", &x, &y); if(x == y) continue;
		G[x].push_back(y);
		G[y].push_back(x);
	}
	tsp = 0; memset(dfn, 0, sizeof(dfn)); memset(low, 0, sizeof(low));
    memset(ans, 0, sizeof(ans)); memset(siz, 0, sizeof(siz));
	for(int i=1; i <= n; i++) if(dfn[i] == 0) tarjan(i, 0);
	for(int i=1; i <= n; i++) printf("%lld\n", ans[i]);
	return 0;
}