Description

Input

Output

Sample Input

7 9
1 2
1 3
1 4
1 5
1 6
1 7
2 3
4 5
6 7

Sample Output

18
6
6
6
6
6
6

Data Constraint

 

Solution

tarjan找割点直接计算即可。对于一个点，若它是割点，那么它的贡献即为删去这个点后不同联通块的size两两相乘的和再除以二，最后加上n-1，(代表以这个点为起点的种数)。若它不是割点，那么它的贡献就是n-1。注意计算两两联通块相乘的和时，考虑x的子树中有返祖边的情况。比如这个情况：n=4,m=4,(u,v)=(1,4),(2,3),(1,2),(2,4)。对于割点的答案应是5。

 

Code

#include<cstdio>
#include<cstring>
#include<algorithm>
#define N 500010
using namespace std;
int n,m,x,y,dfn[N],low[N],sz[N],bz[N],ans[N];
int t[N*4],nx[N*4],l[N];
void add(int x,int y){
	t[++t[0]]=y;
	nx[t[0]]=l[x];
	l[x]=t[0];
}
void tarjan(int x){
	sz[x]=1;
	dfn[x]=low[x]=++dfn[0];
	int sum=0;
	for(int k=l[x];k;k=nx[k]){
		int y=t[k];
		if(!dfn[y]){
			tarjan(y);
			sz[x]+=sz[y];
			low[x]=min(low[x],low[y]);
			if(dfn[x]<=low[y]){
				bz[x]=1;
				ans[x]+=sz[y]*(n-sz[y]-1);
				sum+=sz[y];
			}
		}
		else low[x]=min(low[x],dfn[y]);
	}
	ans[x]+=sum*(n-sum-1);
}
int main(){
	freopen("war.in","r",stdin);
	freopen("war.out","w",stdout);
	scanf("%d%d",&n,&m);
	for(int i=1;i<=m;i++){
		scanf("%d%d",&x,&y);
		add(x,y);add(y,x);
	}
	memset(bz,0,sizeof(bz));
	tarjan(1);
	for(int i=1;i<=n;i++){
		printf("%d\n",ans[i]/2+n-1);
	}
	return 0;
}

 

---

---

作者：zsjzliziyang 
QQ:1634151125 
转载及修改请注明 
本文地址:https://blog.****.net/zsjzliziyang/article/details/86651572