[POI2008]BLO
时间限制: 1 Sec 内存限制: 162 MB
提交: 56 解决: 30
[提交][状态][讨论版]
题目描述
Byteotia城市有n个 towns m条双向roads. 每条 road 连接 两个不同的 towns ,没有重复的road. 所有towns连通。
输入
输入n<=100000 m<=500000及m条边
输出
输出n个数，代表如果把第i个点去掉，将有多少对点不能互通。
样例输入
5 5
1 2
2 3
1 3
3 4
4 5
样例输出
8
8
16
14
8
可以发现，如果一个点是割点，所有被他割断的子节点都会对答案产生贡献（就是这个sz[son]×（n-1-sz[son]）），只要最后<<1就好了。
黄学长的做法极其简单，树规，点双连通分啥的都没必要。
#include <cstdio>
#include <cstdlib>
#include <cstring>
#include <algorithm>
#include <iostream>
#define N 1000005
#define ll long long
using namespace std;
struct road{
int v,next;}lu[N*10];
int n,m,e,adj[N],cnt,dfn[N],low[N];
ll ans[N],sz[N];
inline void add(int u,int v){lu[++e]=(road){v,adj[u]};adj[u]=e;}
inline void gmin(int &x,int y){
if(y<x)x=y;}
void tarjan(int x)
{ll sum=0;low[x]=dfn[x]=++cnt;sz[x]=1;for(int i=adj[x];i;i=lu[i].next){int to=lu[i].v;if(!dfn[to]){tarjan(to);sz[x]+=sz[to];gmin(low[x],low[to]);if(dfn[x]<=low[to]){ans[x]+=sum*sz[to];sum+=sz[to];}}else gmin(low[x],dfn[to]);}ans[x]+=sum*(n-sum-1)*1ll;
}
int main()
{scanf("%d%d",&n,&m);for(int i=1,x,y;i<=m;i++){scanf("%d%d",&x,&y);add(x,y);add(y,x);}tarjan(1);for(int i=1;i<=n;i++)printf("%lld\n",(ans[i]+(n-1)*1ll)<<1);
}