题目描述
Byteotia城市有n个 towns m条双向roads. 每条 road 连接 两个不同的 towns ,没有重复的road. 所有towns连通。
输入
输入n<=100000 m<=500000及m条边
输出
输出n个数，代表如果把第i个点去掉，将有多少对点不能互通。
样例输入
5 5
1 2
2 3
1 3
3 4
4 5
样例输出
8
8
16
14
8
题解
DFS树
Tarjan求点双太暴力了。。。还是选择一个优雅一点的做法——DFS树
考虑在DFS的过程中计算删除每个点的答案。
由于DFS树没有横叉边，只有返祖边，因此一个点把整棵树分为一些部分（下面简称“块”）：父树部分、子树部分。
考虑割掉一个点，什么样的“块”是连通的：由于没有横叉边，因此只有可能是子树“块”与父树“块”相连，然后它们可以连通。即只有所有与父树相连的连通块是相互连通的。
那么就相当于把能够连通的“块”看作1个“块”，于是任意两个不同“块”中的点都是不连通的。
于是就可以将总的点对数减去在同一“块”（这里的“块”指合并以后的）得到答案：$ANS_i=C_n^2-\sum C_{si}^2$。
最后答案需要乘以2，因为题目中的点对是有序点对，需要计算2次。
#include <cstdio>
#include <algorithm>
#define N 100010
#define M 1000010
#define C(n) (((ll)(n) * (n - 1)) >> 1)
using namespace std;
typedef long long ll;
struct edge
{
int to , next;
}a[M];
int n , head[N] , cnt , deep[N] , low[N] , si[N] , num[N];
ll sum[N];
inline void add(int x , int y)
{
a[++cnt].to = y , a[cnt].next = head[x] , head[x] = cnt;
}
void dfs(int x , int fa)
{
int i , ts = 0;
si[x] = 1;
for(i = head[x] ; i ; i = a[i].next)
{
if(a[i].to == fa) continue;
if(!deep[a[i].to])
{
deep[a[i].to] = low[a[i].to] = deep[x] + 1 , dfs(a[i].to , x) , low[x] = min(low[x] , low[a[i].to]) , si[x] += si[a[i].to];
if(low[a[i].to] < deep[x]) ts += si[a[i].to];
else sum[x] += C(si[a[i].to]);
}
else low[x] = min(low[x] , deep[a[i].to]);
}
sum[x] += C(ts + n - si[x]);
}
int main()
{
int m , x , y , i;
scanf("%d%d" , &n , &m);
ll s = C(n);
for(i = 1 ; i <= m ; i ++ ) scanf("%d%d" , &x , &y) , add(x , y) , add(y , x);
deep[1] = 1 , dfs(1 , 0);
for(i = 1 ; i <= n ; i ++ ) printf("%lld\n" , (s - sum[i]) << 1);
return 0;
}