题目传送门(BZOJ)
>原文链接<

题解 :

​ 这是一道 Tarjan 求割点 + 乘法原理计数的题。

求割点 :

设$dfn[p]$是第一次遍历$p$的时间戳,$low[p]$是遍历完$p$的所有子树后,能回到的最早的时间戳。

对于$p$的一个儿子$to$若已经被遍历过,则跳过它并用$dfn[to]$更新$low[p]$

若没有遍历过, 则遍历它并用$low[to]$更新$low[p]$

若$low[to] >= dfn[p]$那么 $p$ 就是割点。

假设把$p$割掉,由于 DFS 的性质,$to$向上走一定会走到$p$而$p$被删除了.而往下走,由于$low$的性质, 显然$to$走不回去,连通性被破坏 $p$是割点。

计数 :

考虑若点$p$是割点,则会把图分成 “上面的一棵大树” + “它的若干子树”

而不能互相联通的点就是那$x+1$棵树中属于两棵不同树的点对。

我们利用乘法原理,设 $p$是割点。记$p$当前已经遍历过子树的$size$和为$t$。那么下一棵子树$to$对答案产生的贡献就是$size[to]\times t$ 而不用考虑更后面的子树,因为它们会向前配对。遍历完所有子树后 答案还要加$(n-\sum size[son]-1)\times t$这是上面那棵大树和它的子树产生的点对。

最后,答案还要加上$n-1$,因为这个点删掉,其他$n-1$个点都不能连通它 ( 说了句废话 )。又因为是有序点对,答案还要乘 2。

代码 :

#include <cstdio>#include <cstring>#include <iostream>#include <algorithm>#define rev(i, p) for(Edge *i = h[p]; i; i = i->next)#define nc() (p1==p2&&(p2=(p1=buf)+fread(buf, 1, 100000, stdin), p1==p2)?EOF:*p1++)using namespace std;char buf[100000],*p1,*p2;inline int rd() { int x = 0; char ch = nc(); while(!isdigit(ch)) ch = nc(); while(isdigit(ch)) x = ((x+(x<<2))<<1)+(ch^48), ch = nc(); return x;}const int N = 110000;struct Edge { int to, val; Edge *next;}*h[N],e[N*10];int dfn[N], low[N], siz[N], n, m;long long ans[N];inline void Add_Edge(int u, int v, int w = 1) { static int _ = 0; Edge *tmp = &e[++_]; tmp->to = v; tmp->val = w; tmp->next = h[u]; h[u] = tmp;}void Tarjan(int p) { int t = 0; siz[p] = 1; dfn[p] = low[p] = ++*dfn; rev(i, p) { if(dfn[i->to]) low[p] = min(low[p], dfn[i->to]); else { Tarjan(i->to); siz[p] += siz[i->to]; low[p] = min(low[p], low[i->to]); if(dfn[p] <= low[i->to]) { ans[p] += (long long)t*siz[i->to]; t += siz[i->to]; } } } ans[p] += (long long)t*(n-t-1);}int main() { n = rd(), m = rd(); for(int i = 1; i <= m; i ++ ) { int u = rd(), v = rd(); Add_Edge(u, v), Add_Edge(v, u); } Tarjan(1); for(int i = 1; i <= n; i ++ ) printf("%lld\n", (ans[i]+n-1)<<1);}