BZOJ 1123 BLO

tarjan求割点计算答案。注意不是每一棵子树都算答案。开个变量记一下。

#include<iostream>

#include<cstdio>

#include<cstring>

#include<algorithm>

#define maxv 100050

#define maxe 1000050

using namespace std;

long long n,m,x,y,g[maxv],nume=,dfn[maxv],low[maxv],stack[maxv],top=,size[maxv],times=,base=,ans[maxv];

bool vis[maxv];

struct edge

{

    long long v,nxt;

}e[maxe];

void addedge(long long u,long long v)

{

    e[++nume].v=v;

    e[nume].nxt=g[u];

    g[u]=nume;

}

void dfs(long long x)

{

    dfn[x]=low[x]=++times;size[x]=;long long t=;vis[x]=true;

    for (long long i=g[x];i;i=e[i].nxt)

    {

        long long v=e[i].v;

        if (!vis[v])

        {

            dfs(v);

            size[x]+=size[v];low[x]=min(low[x],low[v]);

            if (((dfn[x]<=low[v]) && (x!=)) || ((x==) && (base>)))

            {

                stack[++top]=x;

                ans[x]+=t*size[v];

                t+=size[v];

            }

        }

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

    }

    ans[x]+=(n-t-)*t;

    ans[x]*=;

}

int main()

{

    scanf("%lld%lld",&n,&m);

    for (long long i=;i<=m;i++)

    {

        scanf("%lld%lld",&x,&y);

        addedge(x,y);addedge(y,x);

        if ((x==) || (y==)) base++;

    }

    dfs();

    sort(stack+,stack+top+);

    base=unique(stack+,stack+top+)-stack-;

    long long p=;

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

    {

        if (stack[p]==i)

        {

            printf("%lld\n",*(n-)+ans[i]);

            p++;

        }

        else printf("%lld\n",(n-)*);

    }

    return ;

}