传送门:http://www.lydsy.com/JudgeOnline/problem.php?id=1123
题意略坑,仔细读样例
求Tarjan割点
在dfs树中删掉一个点,他的各个子树不连通,子树与原树的其他部分不连通,统计答案
Code:
#include<bits/stdc++.h> using namespace std; const int maxn=1e5+10; vector<int>G[maxn]; int n,m; typedef long long LL; LL anss[maxn]; int low[maxn],dfn[maxn],tot,siz[maxn]; void dfs(int u){ low[u]=dfn[u]=++tot;LL t=0;siz[u]=1; for(int i=0;i<G[u].size();i++){ int v=G[u][i]; if(!dfn[v]){ dfs(v); siz[u]+=siz[v]; low[u]=min(low[u],low[v]); if(dfn[u]<=low[v]){ anss[u]+=t*siz[v]; t+=siz[v]; } }else low[u]=min(low[u],dfn[v]); }anss[u]+=t*(n-t-1); } int main(){ scanf("%d%d",&n,&m); for(int i=1;i<=m;i++){ int u,v;scanf("%d%d",&u,&v); G[u].push_back(v); G[v].push_back(u); }dfs(1); for(int i=1;i<=n;i++) printf("%lld\n",anss[i]*2+(n-1)*2); return 0; }