[bzoj1123] [POI2008]BLO

Description
n个点m条边的无向连通图,无重边无自环.
求对于所有i,去掉第i个点后有多少对有序点不连通.
HINT
\(n\leq100000,m\leq500000\).
Solution
tarjan求割点的时候顺便计数即可.

#define N 100005
#define M 1000005
typedef long long ll;
struct graph{
    int nxt,to;
}e[M];
ll ans[N];
int g[N],dfn[N],low[N],siz[N],n,m,cnt;
bool cut[N];
inline void tarjan(int u,int fa){
    int chl=0,tot=0;
    dfn[u]=low[u]=++cnt;siz[u]=1;
    for(int i=g[u],c;i;i=e[i].nxt)
        if(!dfn[c=e[i].to]){
            tarjan(c,u);
            siz[u]+=siz[c];
            low[u]=min(low[u],low[c]);
            if(!fa){
                if(++chl>=2){
                    cut[u]=true;
                    ans[u]+=1ll*siz[c]*tot;
                    tot+=siz[c];
                }
            }
            else if(low[c]>=dfn[u]){
                cut[u]=true;
                ans[u]+=1ll*siz[c]*tot;
                tot+=siz[c];
            }
        }
        else if(c!=fa)
            low[u]=min(low[u],dfn[c]);
    if(cut[u]) ans[u]+=1ll*(n-1-tot)*tot;
    ans[u]+=n-1;
}
inline void addedge(int x,int y){
    e[++cnt]=(graph){g[x],y};g[x]=cnt;
}
inline void Aireen(){
    n=read();m=read();
    for(int i=1,x,y;i<=m;++i){
        x=read();y=read();
        addedge(x,y);addedge(y,x);
    }
    for(int i=1;i<=n;++i)
        if(!dfn[i]) tarjan(i,0);
    for(int i=1;i<=n;++i)
        printf("%lld\n",ans[i]<<1);
}

2017-10-27 13:11:29