[文章目录]
Description
Byteotia城市有n个 towns m条双向roads. 每条 road 连接 两个不同的 towns ,没有重复的road. 所有towns连通。输出n个数，代表如果把第i个点去掉，将有多少对点不能互通。 n<=10^5 m<=5*10^5
tarjan求点双，建出圆方树后DP计数即可。
#include <cstdio>
#include <cctype>
#include <cstring>
#include <algorithm>
using namespace std;
#define N 101000
#define M 1001000
typedef long long ll;
inline char nc()
{
static char buf[100000],*p1,*p2;
return p1==p2&&(p2=(p1=buf)+fread(buf,1,100000,stdin),p1==p2)?EOF:*p1++;
}
inline int read()
{
int re=0; char ch=nc();
while(!isdigit(ch)) ch=nc();
while(isdigit(ch)) re=re*10+(ch^'0'),ch=nc();
return re;
}
int n,m,tot,head[N],to[M],nxt[M],cnt;
inline void add(int x,int y)
{
to[++cnt]=y; nxt[cnt]=head[x]; head[x]=cnt;
to[++cnt]=x; nxt[cnt]=head[y]; head[y]=cnt;
}
int Head[N<<1],To[N<<2],Nxt[N<<2],Cnt;
inline void Add(int x,int y)
{
To[++Cnt]=y; Nxt[Cnt]=Head[x]; Head[x]=Cnt;
To[++Cnt]=x; Nxt[Cnt]=Head[y]; Head[y]=Cnt;
}
int z[N],top,dfn[N],low[N],tim;
void tarjan(int x,int pre)
{
z[++top]=x; dfn[x]=low[x]=++tim; int y;
for(int i=head[x];i;i=nxt[i]) if(to[i]!=pre)
{
if(!dfn[y=to[i]])
{
tarjan(y,x);
low[x]=min(low[x],low[y]);
if(low[y]>=dfn[x])
{
int t; tot++;
do
{
t=z[top--];
Add(tot,t);
}while(t!=y);
Add(tot,x);
}
}
else low[x]=min(low[x],dfn[y]);
}
}
int siz[N<<1];
ll ans[N<<1];
void dfs(int x,int pre)
{
ll t=0; siz[x]=(x<=n);
for(int i=Head[x];i;i=Nxt[i]) if(To[i]!=pre)
{
dfs(To[i],x);
ans[x]+=t*siz[To[i]];
siz[x]+=siz[To[i]];
t+=siz[To[i]];
}
ans[x]+=t*(n-siz[x]);
}
int main()
{
tot=n=read(); m=read();
while(m--) add(read(),read());
tarjan(1,0);
dfs(1,0);
for(int i=1;i<=n;++i) printf("%lld\n",(ans[i]+(n-1))*2);
return 0;
}