题目描述
在Byteotia有n个城镇。 一些城镇之间由无向边连接。 在城镇外没有十字路口,尽管可能有桥,隧道或者高架公路(反正不考虑这些)。每两个城镇之间至多只有一条直接连接的道路。人们可以从任意一个城镇直接或间接到达另一个城镇。 每个城镇都有一个公民,他们被孤独所困扰。事实证明,每个公民都想拜访其他所有公民一次(在主人所在的城镇)。所以,一共会有n*(n-1)次拜访。

不幸的是,一个程序员总罢工正在进行中,那些程序员迫切要求购买某个软件。

作为抗议行动,程序员们计划封锁一些城镇,阻止人们进入,离开或者路过那里。

正如我们所说,他们正在讨论选择哪些城镇会导致最严重的后果。

编写一个程序:

读入Byteotia的道路系统,对于每个被决定的城镇,如果它被封锁,有多少访问不会发生,输出结果。

输入输出格式
第一行读入n,m,分别是城镇数目和道路数目

城镇编号1~n

接下来m行每行两个数字a,b,表示a和b之间有有一条无向边

输出n行,每行一个数字,为第i个城镇被锁时不能发生的访问的数量。


如果熟悉割点的同学,应该很容易看出来这就是一道割点的题目。

然后我们对于不同的点讨论可得:

对于非割点: 答案就是 2*(n-1),因为非割点不会影响连通性。只是这个点不见了。

对于割点: 答案就是 2*(n-1)再加上每组块的点的数量互相乘出来。


这样就变成了 求割点树形dp求子树的size 的问题了。

对于割点直接 tarjan 即可,当一个点的某一个孩子的 low>= 此点的 dfn时,说明这个点就是割点。因为孩子的low大于当前节点的dfn,说明它没有办法直接从当前节点回到搜索树搜过的节点。如果当前节点删除了,此孩子将会分割开来)。

求子树的size,直接dfs累加即可,可以在tarjan中完成。


AC代码:

#pragma GCC optimize(2)
#include<bits/stdc++.h>
#define int long long
using namespace std;
const int N=1e5+10,M=1e6+10;
int n,m,dfn[N],low[N],cnt,res[N],size[N];
int head[N],nex[M],to[M],tot;
inline void add(int a,int b){
	to[++tot]=b; nex[tot]=head[a]; head[a]=tot;
}
void tarjan(int x){
	dfn[x]=low[x]=++cnt;	int sum=0;	size[x]=1;
	for(int i=head[x];i;i=nex[i]){
		if(!dfn[to[i]]){
			tarjan(to[i]);	size[x]+=size[to[i]];
			low[x]=min(low[x],low[to[i]]);
			if(dfn[x]<=low[to[i]]){
				res[x]+=sum*size[to[i]];
				sum+=size[to[i]];
			}
		}else	low[x]=min(low[x],dfn[to[i]]);
	}
	res[x]+=(n-sum-1)*sum;	res[x]+=(n-1);
}
signed main(){
	scanf("%lld %lld",&n,&m);
	while(m--){
		int a,b;	scanf("%lld %lld",&a,&b);	add(a,b);	add(b,a);
	}
	tarjan(1);
	for(int i=1;i<=n;i++)	printf("%lld\n",res[i]<<1);
	return 0;
}