题目传送门(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向上走一定会走到pp被删除了.而往下走,由于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);}