BLO

内存限制：162 MiB 时间限制：1000 ms 标准输入输出

题目描述

Byteotia城市有n个 towns m条双向roads. 每条 road 连接两个不同的 towns ,没有重复的road. 所有towns连通。

输入格式

输入n<=100000 m<=500000及m条边

输出格式

输出n个数，代表如果把第i个点去掉，将有多少对点不能互通。

样例

样例输入

样例输出

首先如果这个点不是割点，那么显然该点删去后对除了此点以外所有点之间的点对关系不造成影响，影响的只是当前点与其他点之间点对。所以贡献$2*(n-1)$

然后如果这个点是个割点，这个点可以分割后具体可以分成这几部分，

一，直接与原图相连的连通块

二，图剩余部分

三，节点自身

考虑这三部分的贡献

对于二：

它与除了连通块外点构成点对都被拆散

那么贡献为$size[y]\times (n-size[y])$

我们算的是单方向点对

对于三：

它分割以后与其他所有点点对都被拆散

对于一：

我们用一个小容斥，然后贡献类似于二

完了

以下依然是本人丑陋的代码

#include<bits/stdc++.h>
#define ll long long
#define A 1000000
#define read(a) scanf("%lld",&a)
#define put(a) printf("%lld\n",a)
using namespace std;
ll low[A],size[A],dfn[A],head[A],ver[A],nxt[A],tot=0,cut[A],ans[A];
ll n,m,num=0,root;
void add(ll x,ll y){
    ver[++tot]=y;nxt[tot]=head[x];head[x]=tot;return ;
}
void tarjan(ll x){
    low[x]=dfn[x]=++num;size[x]=1;
    ll flag=0,sum=0;
    //若不为割点ans可以被其他n-1个点贡献
    //若为割点ans可以由剩余n-sum-1个点贡献以及这个点不能到达其他任何点以及其他与x直接连接点到达不了其他点
    for(ll i=head[x];i;i=nxt[i]){
        ll y=ver[i];
        if(!dfn[y]){
            tarjan(y);
            size[x]+=size[y];
            
            low[x]=min(low[x],low[y]);
            if(low[y]>=dfn[x]){
                flag++;sum+=size[y];ans[x]+=size[y]*(n-size[y]);
                if(x!=root||flag>1){
                    cut[x]=1;
                }
            }
        }
        else low[x]=min(low[x],dfn[y]);
    }
    if(cut[x]) ans[x]+=(n-sum-1)*(sum+1)+n-1;//,printf("贡献ans[%lld]=%lld\n",x,ans[x]);
    else ans[x]=2*(n-1);//,printf("贡献ans[%lld]=%lld 2*(n-1)=%lld\n",x,ans[x],2*n-1);
}
int main(){
        read(n),read(m);
        for(ll i=1;i<=m;i++){
            ll xx,yy;read(xx),read(yy);add(xx,yy);add(yy,xx);
        }
        for(ll i=1;i<=n;i++)
            if(!dfn[i])root=i,tarjan(i);
        for(ll i=1;i<=n;i++){
            //printf("size[i]=%lld cut[%lld]=%lld\n",size[i],i,cut[i]);
            put(ans[i]);
        }
}

View Code

注意

            if(low[y]>=dfn[x]){
                flag++;sum+=size[y];ans[x]+=size[y]*(n-size[y]);
                if(x!=root||flag>1){
                    cut[x]=1;
                }
            }

中sum ans都要放在判断割点之上，因为我们算的在根上也要照常计算