版本：2022年11月第1版

页码：436

相关算法： tarjan 割点

相关题目：link

一个简单的例子：

输出显然为4 4 4，而书上代码输出为6 4 4。

（就是没特判根节点就计算了贡献，具体见代码）

//code by xiaozhangma
#include<bits/stdc++.h>
#define LL long long
#define F(x,s,t) for(int x=s;x<=t;x++)
using namespace std;
int read(){
	int x=0,f=1;
	char ch=getchar();
	while(!isdigit(ch)){if(ch=='-')f=-1;ch=getchar();}
	while(isdigit(ch)){x=x*10+ch-'0';ch=getchar();}
	return x*f;
}
void write(int x){
	if(x < 0)putchar('-'),x = -x;
	if(x > 9)write(x / 10);
	putchar(x % 10 + '0');
}
const int N = 1e5 + 10, M = 5e5 + 10;
int head[N], ver[M << 1], nx[M << 1];
int dfn[N], low[N], size[N];
int n, m, tot, num;
LL ans[N];
bool cut[N];
void add(int x, int y){
	ver[++tot] = y, nx[tot] = head[x], head[x] = tot;
}
void tarjan(int x){
	dfn[x] = low[x] = ++num, size[x] = 1;
	int flag = 0, sum = 0;
	for(int i = head[x]; i; i = nx[i]){
		int y = ver[i];
		if(!dfn[y]){
			tarjan(y);
			size[x] += size[y];
			low[x] = min(low[x], low[y]);
			if(low[y] >= dfn[x]){
				flag ++ ;
				/*
				ans[x] += 1ll * size[y] * (n - size[y]);
				if( x != 1 || flag > 1)cut[x] = true;
				注释内为书上代码 
				*/
				if( x != 1 || flag > 1){
					sum += size[y];
					cut[x] = true;
					ans[x] += 1ll * size[y] * (n - size[y]);
				}//正解 
			}
		}else{
			low[x] = min(low[x], dfn[y]);
		}
	}
	if(cut[x]){
		ans[x] += 1ll * (n - sum - 1) * (sum + 1) + (n - 1);
	}else{
		ans[x] += 2 * (n - 1);
	}
}
int main(){
	n = read(), m = read();
	tot = 1;
	F(i, 1, m){
		int x = read(), y = read();
		if(x == y)continue;
		add(x, y), add(y, x);
	}
	tarjan(1);
 
	F(i, 1, n){
		printf("%lld\n", ans[i]);
	}
	return 0;
}
/*
input:
3 3
1 2 
2 3 
1 3
output:
4
4 
4
*/

会用github的大佬可以去[这里]勘误(https://github.com/lydrainbowcat/tedukuri)