洛谷P3469[POI2008] BLO-Blockade（割点）
题目描述
在Byteotia有n个城镇。 一些城镇之间由无向边连接。 在城镇外没有十字路口，尽管可能有桥，隧道或者高架公路（反正不考虑这些）。每两个城镇之间至多只有一条直接连接的道路。人们可以从任意一个城镇直接或间接到达另一个城镇。 每个城镇都有一个公民，他们被孤独所困扰。事实证明，每个公民都想拜访其他所有公民一次（在主人所在的城镇）。所以，一共会有n*（n-1）次拜访。
不幸的是，一个程序员总罢工正在进行中，那些程序员迫切要求购买某个软件。
作为抗议行动，程序员们计划封锁一些城镇，阻止人们进入，离开或者路过那里。
正如我们所说，他们正在讨论选择哪些城镇会导致最严重的后果。
编写一个程序：读入Byteotia的道路系统，对于每个被决定的城镇，如果它被封锁，有多少访问不会发生，输出结果。
输入输出格式
第一行读入n，m，分别是城镇数目和道路数目
城镇编号1~n
接下来m行每行两个数字a,b，表示a和b之间有有一条无向边
输出n行，每行一个数字，为第i个城镇被锁时不能发生的访问的数量。
输入
5 5
1 2
2 3
1 3
3 4
4 5
输出
8
8
16
14
8
题意
给定一张图，有n个点，m条边，题目保证一开始各个点都是相通的。每个点都要访问其他的点，因此总访问数是n*(n-1)。题目要求删除每个点一次，从点1删到点n，问删除每个点不能发生访问的数量。
如果i不是割点，删除i不会影响其他点的互相到达，那么不能发生的访问数就是i到其他点的次数(n-1)以及其他点到i的次数(n-1)，就是2*(n-1)。
如果i是割点，那么删除i会把图分为a个连通块以及i本身，由于tarjan在求割点的过程中是一棵搜索树往下遍历，所以除了它和它的子树外，还会有其他剩余点共同构成另一个连通块（有点类似树的重心的求法）。设i所有子树的和为sum，第i个子树的节点总数为size[i]。
删除u后以v为根的子树内的所有点都无法访问其它点,这部分贡献：∑size[v]×(n?size[v])，size一开始都是1。
删除割点u后割点和其它点不连通(这里只用统计一次)，贡献：n?1。
删除割点u后不连通的部分和其它部分不连通，贡献(n?1?sum)×(sum+1)，sum=∑size[v]
#include<iostream>
#include<string>
#include<cstring>
#include<cmath>
#include<cstdio>
#include<queue>
#include<stack>
#include<vector>
#include<algorithm>
#include<functional>
#include<map>
#include<unordered_map>
#define lowbit(x) ((x)&-(x))
using namespace std;
typedef long long ll;
typedef unsigned long long ull;
const ll N=1e6+10,NN=2e3+10,INF=0x3f3f3f3f,LEN=20;
const ll MOD=1e9+7;
const ull seed=31;
inline ll read(){ll x=0,f=1;char ch=getchar();while(ch<'0'||ch>'9'){if(ch=='-') f=-1;ch=getchar();}while(ch>='0'&&ch<='9'){x=(x<<1)+(x<<3)+(ch^48);ch=getchar();}return x*f;
}
struct Edge{ll next,to;
}edge[N];
ll n,m,num_edge,dfn;
ll head[N],num[N],low[N],size[N],ans[N];
bool iscut[N];
void add_edge(ll from,ll to){edge[num_edge].next=head[from];edge[num_edge].to=to;head[from]=num_edge++;
}
void tarjan(ll u,ll fa){ll child=0,sum=0;size[u]=1;num[u]=low[u]=++dfn;for(ll i=head[u];i!=-1;i=edge[i].next){ll v=edge[i].to;if(!num[v]){++child;tarjan(v,u);size[u]+=size[v];low[u]=min(low[u],low[v]);if(low[v]>=num[u]){if(fa!=-1) iscut[u]=true;ans[u]+=size[v]*(n-size[v]);//u的孩子不能到u与u的祖先的次数 sum+=size[v];}}else low[u]=min(low[u],num[v]);}if(fa==-1&&child>=2) iscut[u]=true;if(iscut[u]) ans[u]+=(n-sum-1)*(sum+1)+(n-1);//(n-sum-1)*(sum+1)为祖先不能到u与u的孩子的次数，(n-1)为u不能到各个点的次数 else ans[u]=2*(n-1);//处理u不是割点的情况
}
void init(){num_edge=dfn=0;memset(head,-1,sizeof head);memset(low,0,sizeof low);memset(num,0,sizeof num);memset(ans,0,sizeof ans);memset(size,0,sizeof size);memset(iscut,false,sizeof iscut);
}
int main(){while(~scanf("%lld%lld",&n,&m)){init();for(ll i=1;i<=m;i++){ll u,v;scanf("%lld%lld",&u,&v);add_edge(u,v);add_edge(v,u);}for(ll i=1;i<=n;i++) if(!num[i]) tarjan(i,-1);//其实直接tarjan(1,-1)即可，因为保证不删除点的时候是连通的for(ll i=1;i<=n;i++) printf("%lld\n",ans[i]);}
}