BZOJ 1123 [POI2008]BLO 点双连通分量

题意:链接方法:点双连通分量解析:这题样例还看了一会…就是所有的点对是有序的，，并且删掉的点也算。所以不是割点的点删掉之后答案是固定的。如果是割点的点的话我们只需要在tarjan里面加点东西就行了。我们记录一个siz，如果某个点可以搜到low比它的deep值大的点的话，显然是产生了一个分割后的连通块？动态乘以下即可。千万别忘了最后乘的一下:)代码:;ll;int n,m;int head[N];int deep[N];int low[N];ll siz[N];ll ans[N];int cnt,tot;struct node{int from,to,next;}edge[M<<1];void init(){memset(head,-1,sizeof(head));cnt=1;}void edgeadd(int from,int to){edge[cnt].from=from;edge[cnt].to=to;edge[cnt].next=head[from];head[from]=cnt++;}void tarjan(int x){ll t=0;deep[x]=low[x]=++tot;siz[x]=1;for(int i=head[x];i!=-1;i=edge[i].next){int to=edge[i].to;if(!deep[to]){tarjan(to);siz[x]+=siz[to];low[x]=min(low[x],low[to]);if(low[to]>=deep[x]){ans[x]+=t*siz[to];t+=siz[to];}}else low[x]=min(low[x],deep[to]);}ans[x]+=t*(n-t-1);}int main(){init();scanf(“%d%d”,&n,&m);for(int i=1;i<=m;i++){int x,y;scanf(“%d%d”,&x,&y);edgeadd(x,y);edgeadd(y,x);}tarjan(1);for(int i=1;i<=n;i++)printf(“%lld\n”,(ans[i]+(n-1))<<1);}

找一个让心里安静和干净的地方，