【NOIP2016提高A组模拟9.15】Map

本文主要是介绍【NOIP2016提高A组模拟9.15】Map，希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！

Description

这里写图片描述

Input

这里写图片描述

Output

所有询问的和

Sample Input

4 4 2
1 2
2 3
3 2
3 4
1 2
1 4

Sample Output

14
样例解释：
upd:保证原图连通。
“不相交路径”的定义为不存在相同的边。可以存在相同的点。重边视为不同的边。
对于样例：
原图有2个安全点对为(2,3),(3,2)
询问1答案为4，新增的安全点对为(1,2),(1,3),(2,1)(3,1)
询问2答案为10，新增的安全点对为(1,2),(1,3),(1,4),(2,1)(2,4),(3,1),(3,4),(4,1),(4,2),(4,3)
因此输出14

Data Constraint

$n,q<=2*10^5$
$m<=4*10^5$
30%图为一棵树

Solution

新增的安全点对肯定在一个环上
先考虑图为一棵树的情况
每次添加一条边，就会多一个环，环的大小可以通过LCA求出
答案增加相应数量就行了
那么对于一张图怎么办？Tarjan缩环，而缩环后的点的点权就是原来环的点的数量
设环上有k个点，每个点的点权为c[i]
那最后增加的答案就是
$(\sum_{i=1}^k c[i])^2-\sum_{i=1}^k c[i]^2$

Code

#include<cstdio>
#include<cstring>
#include<algorithm>
#define fo(i,a,b) for(int i=a;i<=b;i++)
#define fd(i,a,b) for(int i=a;i>=b;i--)
#define N 200100
#define ll long long
using namespace std;
int n,m,tot=1,last[N*10],next[N*10],to[N*10],b[N*10][2],p[N],dfn[N],low[N],sy[N],f[N][18],deep[N],bz[N],bz2[N],totot=0;
ll g[N][18],sn[N],g1[N][18];
void putin(int x,int y)
{
    if (x==y) return;
    next[++tot]=last[x];last[x]=tot;to[tot]=y;
    next[++tot]=last[y];last[y]=tot;to[tot]=x;
}
void tarjan(int x,int fa)
{
    low[x]=dfn[x]=++tot;p[++p[0]]=x;bz[x]=bz2[x]=1;
    for(int i=last[x];i;i=next[i])
    {
        int y=to[i];if(i==(fa^1)) continue;
        if(!bz[y]) tarjan(y,i),low[x]=min(low[x],low[y]);
        else if(bz2[y]) low[x]=min(low[x],dfn[y]);
    }
    if(low[x]==dfn[x])
    {
        totot++;
        for(;p[p[0]+1]!=x;p[0]--)
        {
            int k=p[p[0]];sy[k]=totot;sn[totot]++;bz2[k]=0;
        }
    }
}
ll sqr(ll x){return x*x;}
void dfs(int x)
{
    bz[x]=1;
    for(int i=last[x];i;i=next[i])
    {
        int y=to[i];
        if(bz[y]) continue;
        deep[y]=deep[x]+1;f[y][0]=x;g1[y][0]=sn[y];g[y][0]=sqr(sn[y]);
        dfs(y);
    }
}
ll lca(int x,int y)
{
    ll a=0,b=0;
    fd(i,17,0) if(deep[f[x][i]]>=deep[y]) a+=g1[x][i],b+=g[x][i],x=f[x][i];
    fd(i,17,0) if(deep[f[y][i]]>=deep[x]) a+=g1[y][i],b+=g[y][i],y=f[y][i];
    fd(i,17,0) if(f[x][i]!=f[y][i]) a+=g1[x][i],b+=g[x][i],x=f[x][i],a+=g1[y][i],b+=g[y][i],y=f[y][i];
    if(x!=y) a+=g1[x][0]+g1[y][0],b+=g[x][0]+g[y][0],x=f[x][0];
    a+=g1[x][0],b+=g[x][0];
    return sqr(a)-b;
}
int main()
{
    int ac;scanf("%d %d %d",&n,&m,&ac);
    fo(i,1,n) sy[i]=i;
    fo(i,1,m)
    {
        int x,y;scanf("%d%d",&x,&y);
        putin(x,y);b[i][0]=x;b[i][1]=y;
    }
    tot=0;tarjan(1,-1);
    memset(last,0,sizeof(last));tot=1;memset(bz,0,sizeof(bz));
    fo(i,1,m) putin(sy[b[i][0]],sy[b[i][1]]);
    deep[1]=1;g1[1][0]=sn[1];g[1][0]=sqr(sn[1]);dfs(1);
    ll ans=0;
    fo(j,1,17)
        fo(i,1,n)
        {
            f[i][j]=f[f[i][j-1]][j-1];
            if(f[i][j]) g[i][j]=g[i][j-1]+g[f[i][j-1]][j-1],g1[i][j]=g1[i][j-1]+g1[f[i][j-1]][j-1];
        }
    for(;ac;ac--)
    {
        int x,y;scanf("%d%d",&x,&y);
        ans+=lca(sy[x],sy[y]);
    }
    printf("%lld",ans);
}