题目描述
Byteotia城市有n个 towns m条双向roads. 每条 road 连接 两个不同的 towns ,没有重复的road. 所有towns连通。
输入
输入n<=100000 m<=500000及m条边
输出
输出n个数，代表如果把第i个点去掉，将有多少对点不能互通。
样例输入
5 5
1 2
2 3
1 3
3 4
4 5
样例输出
8
8
16
14
8
易得是割点板子题
对于图上每个割点（非割点无法对答案进行贡献）而言，设其将原连通图分为k个不相连通的子图，第i个子图元素个数为x[i]，于是该割点对答案的贡献为Σx[i]*x[j](i!=j,i,j∈x）。
同时观察样例我们可以知道，所谓不能互通的点具有顺序（比如（1,2）和（2,1））。
我们又知道，对于tarjan算法中一棵搜索树，一共包含两个部分：
（1）由割点引出的很多棵子树。
（2）与割点父亲相连通的所有点。
（3）割点本身。

其中绿、蓝、黄分别是第1、2、3部分。
为了方便起见，我们在下文中将这三部分用1、2和3表示。
所以我们可以将答案分成以下几个部分:
(1)搜索树上每棵由根节点引出的子树向其它点连通的点对（包括了1内部的点对、1向2连通的点对、1向3连通的点对）
(2)与割点父亲连通的点向割点连通的点对（2向3）
(3)割点向所有点连通的点对（3向1、2）
(4)与割点父亲连通的点向根节点子树连通的点对(2向1）
第一部分很容易处理，我们设每棵根节点prev向外引出的子树元素个数为subtree[prev]，则其余点的个数共(n-subtree[prev])个，于是我们可以将subtree[prev]*(n-subtree[prev])贡献到答案ans[x]中；（注意x是每个prev的父亲）
第二部分，我们设所有割点引出的子树（不包含割点自己）元素个数总和为sum，因为每次讨论的割点只有一个，其余点就有(n-sum-1)个，则我们可以将(n-sum-1)贡献到答案ans[x]中；
第三部分更容易处理，因为每次讨论的割点只有一个，其它点有（n-1）个，于是我们将（n-1）贡献到答案中；
第四部分，我们将sum*（n-sum-1）贡献到答案中。
于是，对于每个割点x,有ans[x]=∑subtree[prev]*(n-subtree[prev])+(n-sum-1)+(n-1)+sum*(n-sum-1)=∑subtree[prev]*(n-subtree[prev])+(n-sum-1)+(sum+1)*(n-sum-1);
对于非割点x,有ans[x]=2*(n-1）（只有割点本身受影响）。
关于统计subtree数组，我们每次进入函数时将subtree[x]置为1（表示这棵树只有根节点一个节点），然后在tarjan（y）回溯时令tarjan[x]=tarjan[y]+1即可。这种类似前缀和的树上技巧需要我们学习。
上代码
#include<iostream>
#include<cstdio>
#include<cstring>
using namespace std;
int head[100050],num,n,m,cut[100050],dfn[100050],subtree[100050],low[100050],root,cnt;
long long ans[100050];
struct edge
{
    int u,v,nxt;
}e[2000050];
void add(int u,int v)
{
    e[num].u=u,e[num].v=v;
    e[num].nxt=head[u],head[u]=num++;
}
void tarjan(int x,int in_edge)/*这里用到一个技巧，对于每个点x记录上一个点搜索到x的边的编号，因为是无向图，则其反向边的编号必为in_edge^1（可以自己算一下），但需要注意邻接表必须从0开始存*/
{
    dfn[x]=low[x]=++cnt;
    subtree[x]=1;
    int flag=0,sum=0;
    for(int st=head[x];st!=-1;st=e[st].nxt)
    {
        int y=e[st].v;
        if(!dfn[y])
        {
            tarjan(y,st);
            subtree[x]+=subtree[y];
            low[x]=min(low[x],low[y]);
            if(low[y]>=dfn[x])
            {
                sum+=subtree[y];
                ans[x]+=(long long)subtree[y]*(n-subtree[y]);//（1）
                flag++;
                if(x!=root||flag>1)cut[x]=1;
            }
        }
        else if(st!=(in_edge^1))//注意这个地方，异或运算的优先级低于比较，所以必须加括号
        {
            low[x]=min(low[x],dfn[y]);
        }
    }
    if(cut[x]) {
        ans[x]+=(long long)(n-sum-1)*(sum+1)+(n-1);//（2）（3）（4）
    }
    else ans[x]=2*(n-1);//不是割点则不影响其它点
}
int main()
{
    memset(head,-1,sizeof head);
    scanf("%d%d",&n,&m);
    int a,b;
    for(int i=1;i<=m;i++)
    {
        scanf("%d%d",&a,&b);
        add(a,b);
        add(b,a);
    }//注意是无向图
    root=1;
    for(int i=1;i<=n;i++)//处理不连通图
        if(!dfn[i])root=i,tarjan(i,-1);
    for(int i=1;i<=n;i++)printf("%lld\n",ans[i]);//注意不开longlong会炸
    return 0;
}

 

版权声明：本文为qxds原创文章，遵循 CC 4.0 BY-SA 版权协议，转载请附上原文出处链接和本声明。
本文链接：https://www.cnblogs.com/qxds/p/11232702.html