割点的好题。
联通图，难度降低。首先对于一个点，如果他不是割点，那它的贡献是2*(n-1)，就是任何一个其他节点都少了正反两个数对，这个看样例可以看出来。
如果它是一个割点，去掉他以后会出现若干个联通块，而这些联通块两两之间不相连，把它们的大小两两相乘即可。
我们知道，在进行tarjan时会跑出一颗搜索树，我们直接记size[x]表示以x为根节点的子树大小，在找到一个割点时，low值大于dfn[x]的子树们各自为家，剩下的会构成另一棵大的子树。这样的话，根据（乘法结合律）原理即可得出:
ans[x]=size[s1]*(n-size[s1])+size[s2]*(n-size[s2])+……+1*(n-1)+(n-1-∑k=1->tsize[sk])*(1+∑k=1->tsize[sk]) （抄式子就是爽）。
一开始NC了，把sum放判断外面了，那这样更出来的sum就不是能作出上式贡献的size了。
#include<iostream> #include<algorithm> #include<cmath> #include<cstring> #include<cstdio> #include<vector> #include<queue> #include<stack> #include<set> #include<map> using namespace std; int read(){ int sum=0,f=1;char x=getchar(); while(x<‘0‘||x>‘9‘){ if(x==‘-‘) f=-1; x=getchar(); }while(x>=‘0‘&&x<=‘9‘){ sum=sum*10+x-‘0‘; x=getchar(); }return sum*f; } struct EDGE{ int ed,nex; }edge[1000500];int first[100500],num; int n,m,ord,root=1; int dfn[100500],low[100500]; bool cut[100500]; long long ans[100500],size[100500]; void add(int st,int ed){ edge[++num].ed=ed; edge[num].nex=first[st]; first[st]=num; } void tarjan(int x){ dfn[x]=low[x]=++ord; size[x]=1; int child=0,sum=0; for(int i=first[x];i;i=edge[i].nex){ int y=edge[i].ed; if(!dfn[y]){ tarjan(y); size[x]+=size[y]; low[x]=min(low[x],low[y]); if(low[y]>=dfn[x]){ child++; ans[x]+=1ll*size[y]*(n-size[y]); sum+=size[y]; } }else low[x]=min(low[x],dfn[y]); }if((x!=root&&child>0)||(x==root&&child>=2)) /*cout<<"cut is "<<x<<endl,*/ ans[x]+=1ll*(n-1-sum)*(sum+1)+n-1; else ans[x]=2*(n-1); } int main(){ n=read();m=read(); for(int i=1,x,y;i<=m;i++){ x=read();y=read(); add(x,y);add(y,x); } tarjan(root); /* for(int i=1;i<=n;i++) cout<<size[i]<<" ";cout<<endl;*/ for(int i=1;i<=n;i++) printf("%lld\n",ans[i]); return 0; }
原文：https://www.cnblogs.com/Yu-shi/p/11181882.html
