【bzoj1123】【[POI2008]BLO】tarjan判割点

（上不了p站我要死了，侵权度娘背锅）

很明显的判割点

写来练练手，熟悉模板

割点的子树和其他部分不连通，除去子树的剩余部分与子树不连通。乘法原理。

注意会爆int

代码

#include<cstdio>

#include<cstring>

#include<algorithm>

#define ll long long

using namespace std;

inline int read(){

    int k=1,x=0;char ch=0;

    while(ch<'0'||ch>'9'){if(ch=='-')k=-1;ch=getchar();}

    while(ch>='0'&&ch<='9'){x=(x<<3)+(x<<1)+ch-'0';ch=getchar();}

    return x*k;

}

const int N=100000+5;

const int M=500000+5;

int n,m;

int head[N],end[M*2],nxt[M*2],hh=1;

int idc,dfn[N],low[N];

ll siz[N],ans[N];

bool vis[M*2];

void adde(int a,int b){

    hh++;

    end[hh]=b;

    nxt[hh]=head[a];

    head[a]=hh;

}

void tarjan(int u){

    idc++;

    dfn[u]=low[u]=idc;

    siz[u]=1,ans[u]=n-1;

    bool bj=0;

    ll cnt=0,sizz=1;

    for(int i=head[u];i;i=nxt[i]){

        if(vis[i]) continue;

        cnt++;

        vis[i]=vis[i^1]=1;

        int v=end[i];

        if(dfn[v]){

            low[u]=min(low[u],dfn[v]);

        }

        else{

            tarjan(v);

            siz[u]+=siz[v];

            low[u]=min(low[v],low[u]);

            if(low[v]>=dfn[u]){

                bj=1;

                ans[u]+=siz[v]*(n-siz[v]);

                sizz+=siz[v];

            }

        }

    }

    if(u==1&&cnt<=1) ans[u]=(n-1)*2;

    if(u!=1&&bj==0) ans[u]=(n-1)*2;

    if(u!=1&&bj||u==1&&cnt>1) ans[u]+=(n-sizz)*sizz;

}

int main(){

    n=read(),m=read();

    for(int i=1;i<=m;i++){

        int a,b;

        a=read(),b=read();

        adde(a,b),adde(b,a);

    }

    tarjan(1);

    for(int i=1;i<=n;i++) printf("%lld\n",ans[i]);

    return 0;

}