算法竞赛进阶指南，399页, 图的割点
本题要点：
1、用 ans[i]记录每一个点去除之后的答案：
如果 i点不是割点，去除i点后，答案应该是 2 * (n - 1), 原图分为了两个连通块 ，i 点 和其他部分；
如果 i点是割点， i点的 所有的子节点中，有 t个（假设为 s[1], s[2], …, s[k]）满足 dfn[i] <= low[s[k]],
1）那么原图最多有 t + 2 个连通块
2）节点 i 自身为一个连通块，
3）有 t 个连通块，由搜索树上以 s[j] (1 <= j <= t) 为根节点的子树构成
剩下的点可能是一个连通块。
2、size[i] 表示以i为根节点的子树的 一共包含几个点， 遍历到某点x ， ans[x]:
ans[i] = size[s[1]] * (n - size[s[1]]) + size[s[2]] * (n - size[s[2]]) + … + size[s[t]] * (n - size[s[t]])
+ 1 * (n - 1) + (n - 1 - sum{s[1], s[2], …, s[t]})(1 + sum{s[1], s[2], …, s[t]})
3、使用 long long
#include <cstdio>
#include <cstring>
#include <iostream>
using namespace std;
const int MaxN = 100010, MaxM = 500010;
int head[MaxN], ver[MaxM * 2], Next[MaxM * 2];
int dfn[MaxN], low[MaxN], size[MaxN]; //size[i] 表示以i为根节点的子树的 一共包含几个点
long long ans[MaxN];
bool cut[MaxN]; //某个点是否是割点
int n, m, tot, num, root;void add(int x, int y)
{
ver[++tot] = y, Next[tot] = head[x], head[x] = tot;
}void tarjan(int x)
{
dfn[x] = low[x] = ++num;int flag = 0, sum = 0;for(int i = head[x]; i; i = Next[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] += (long long)size[y] * (n - size[y]);sum += size[y];if(x != 1 || flag > 1){
cut[x] = true;}}}else{
low[x] = min(low[x], dfn[y]);}}size[x]++;if(cut[x]){
ans[x] += (long long)(n - sum - 1) * (sum + 1) + (n - 1);}else{
ans[x] = 2 * (n - 1);}
}int main()
{
int x, y;scanf("%d%d", &n, &m);for(int i = 1; i <= m; ++i){
scanf("%d%d", &x, &y);if(x == y) continue;add(x, y);add(y, x);}tarjan(1);for(int i = 1; i <= n; ++i){
printf("%lld\n", ans[i]);}return 0;
}/* 5 5 1 2 2 3 1 3 3 4 4 5 *//* 8 8 16 14 8 */