分析:这个题要大力分类讨论
首先如果一个点不是割点的话,显然删掉它后就只有它访问别人和别人访问它不能实现\(ans[u] = 2(n-1)\)
如果它是割点的话就比较复杂了,我们用\(Tarjan\)算法处理的时候顺便求一下
首先设\(s[v]\)表示删掉\(u\)这个点后,以\(v\)为根的子树和图不再连通(树指深搜树),\(s[v]\)为以\(v\)为根的子树大小
\(1.\)删除\(u\)后以\(v\)为根的子树内的所有点都无法访问其它点,这部分贡献\(\sum s[v] \times (n - 1 - s[v])\)
\(2.\)删除割点\(u\)后割点和其它点不连通(这里只用统计一次),贡献:\(n-1\)
\(3.\)删除割点\(u\)后不连通的部分和其它部分不连通,贡献\((n-1-sum) \times (sum + 1)\),\(sum = \sum s[v]\)
综上所述:
\(ans[u] = \sum s[v] \times (n - 1 - s[v]) + (n-1) + (n-1-sum) \times (sum + 1)\)
#include <cstdio>
#include <cctype>
#include <vector>
#include <algorithm>
typedef long long ll;
using namespace std;
const int maxn = 1e5 + 100;
inline int read(){
int x = 0;char c = getchar();
while(!isdigit(c))c = getchar();
while(isdigit(c))x = x * 10 + c - '0',c = getchar();
return x;
}
vector<int> G[maxn];
inline void addedge(int from,int to){G[from].push_back(to);}
ll ans[maxn];
int dfn[maxn],low[maxn],siz[maxn],iscut[maxn],n,m,tot;
inline void tarjan(int u,int faz){
dfn[u] = low[u] = ++tot;
siz[u] = 1;
int child = 0;ll sum = 0;
for(int v : G[u]){
if(!dfn[v]){
tarjan(v,u);child++;
siz[u] += siz[v];
low[u] = min(low[u],low[v]);
if(dfn[u] <= low[v]){
iscut[u] = 1;
ans[u] += (ll)siz[v] * (n - siz[v]);
sum += siz[v];
}
}else if(v != faz)low[u] = min(low[u],dfn[v]);
}
if(faz < 0 && child == 1)iscut[u] = 0;
if(iscut[u])ans[u] += (n - 1) + ll(n - 1 - sum) * (1 + sum);
else ans[u] = 2 * ll(n - 1);
}
int main(){
n = read(),m = read();
for(int u,v,i = 1;i <= m;i++)
u = read(),v = read(),addedge(u,v),addedge(v,u);
tarjan(1,-1);
for(int i = 1;i <= n;i++)
printf("%lld\n",ans[i]);
return 0;
}题解 P3469 【[POI2008]BLO-Blockade】
原文：https://www.cnblogs.com/colazcy/p/11622795.html