【洛谷P3469】[POI2008]BLO-Blockade

BLO-Blockade

题目链接

若一个点为割点：统计出每个子树的大小，两两相乘再相加，

　　　　　　　　再加上n-1，为这个点与其他点的拜访数，

　　　　　　　　因为拜访是互相的，最后再乘二即可

若一个点不是割点：只有(n-1)*2次拜访会受影响

#include<cstdio>

#define LL long long

#define N 100010

#define M 1000010

#define min(a,b) ((a)<(b)?(a):(b))

int n,m,dfn[N],low[N],size[N],cnt;

LL ans[N];

const int ch_top=4e7+;

char ch[ch_top],*now_r=ch-,*now_w=ch-;

inline int read(){

    while(*++now_r<'');

    register int x=*now_r-'';

    while(*++now_r>='')x=x*+*now_r-'';

    return x;

}

inline void write ( LL x ) {

    static char st[] ; static int top ;

    if ( x <  ) *++now_w = '-' , x *= - ;

    while( st[++top] = x %  ^  , x /=  ) ;

    while( *++now_w = st[top] , --top );

    *++now_w = '\n' ;

}

int Head[N],num;

struct NODE{

    int to,next;

} e[M];

void Tarjan(int u){

    dfn[u]=low[u]=++cnt;

    size[u]=; int t=;

    for(int i=Head[u];i;i=e[i].next){

        int v=e[i].to;

        if(!dfn[v]){

            Tarjan(v);

            size[u]+=size[v];

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

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

                ans[u]+=(LL)t*size[v];

                t+=size[v];

            }

        }

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

    }

    if(n-t->) ans[u]+=(LL)(n-t-)*t;

}

int main()

{

    fread(ch,,ch_top,stdin);

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

    int x,y;

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

        x=read(); y=read();

        e[++num].to=y;

        e[num].next=Head[x];

        Head[x]=num;

        e[++num].to=x;

        e[num].next=Head[y];

        Head[y]=num;

    }

    Tarjan();

    for(int i=;i<=n;i++)

        write((ans[i]+n-)<<);

    fwrite(ch,,now_w-ch,stdout);

    return ;

}