这道题很明显是要寻找割点。
如果一个点x不是割点，那么删去它之后只会使<x，除x外的其他点>，<除x外的其他点，x>这2*(n-1)个有序对不连通。
如果x是割点，设si是x的子节点，subtree(si)为以si为根的搜索子树，size[si]为这个子树包含的节点数，t为使x为割点的子节点的个数，那么删去x后，<subtree(si)，除subtree(si)的其他点>，<x，除x外的其他点>，<x的所有祖先节点，subtree(x)>这些有序对不连同，那么ans[x]=$sum ^{t}_{k=1}sizeleft[ s_{k} ight] left( n-sizeleft[ s_{k} ight] ight)$ + 1 * (n - 1) + $left( n-1-sum ^{t}_{k=1}sizeleft[ s_{k} ight] ight)$ + $left( 1+sum ^{t}_{k=1}sizeleft[ s_{k} ight] ight)$
如何判断割点？tarjan算法，如果一个点u，与他的一个子节点v，满足dfn[u] ≤ low[v]，那么u就是割点。简单来说，就是点u的有一个子树，子树中所有点能到达的点的最小时间戳都大于等于u的时间戳，说明这个子树中没有点能通过一条边跳过u到达这个子树外的其他点。
要解决这道题，不妨在tarjan深搜的时候顺便算出子树的size，从而算出答案。
#include <iostream> #include <stdio.h> #include <stdlib.h> #include <string.h> #define MAXN 100010 #define MAXM 500010 using namespace std; typedef long long LL; int n,m; int to[MAXM*2],nxt[MAXM*2],head[MAXN],tot=1; int dfn[MAXN],low[MAXN],size[MAXN],cut[MAXN],num=0; LL ans[MAXN]; void add(int u,int v) { to[++tot]=v;nxt[tot]=head[u];head[u]=tot; } void tarjan(int u) { dfn[u]=low[u]=++num; size[u]=1; int flag=0,sum=0; for(int i=head[u];i;i=nxt[i]) { int v=to[i]; if(!dfn[v]) { tarjan(v); low[u]=min(low[u],low[v]); size[u]+=size[v]; if(dfn[u]<=low[v]) { flag++; ans[u]+=(LL)size[v]*(n-size[v]); sum+=size[v]; if(u!=1||flag>1) cut[u]=true; } } else low[u]=min(low[u],dfn[v]); } if(cut[u]) ans[u]+=(LL)(n-sum-1)*(sum+1)+(n-1); else ans[u]=2*(n-1); } int main() { scanf("%d%d",&n,&m); for(int i=1,u,v;i<=m;i++) { scanf("%d%d",&u,&v); add(u,v);add(v,u); } for(int i=1;i<=n;i++) if(!dfn[i]) tarjan(i); for(int i=1;i<=n;i++) printf("%lld ",ans[i]); return 0; }