题目描述

输入

输出

样例输入

4 4 2

1 2

2 3

3 2

3 4

1 2

1 4

样例输出

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

解法

利用边双连通分量缩点，再利用lca统计答案。

代码

#include<iostream>

#include<stdio.h>

#include<math.h>

#include<string.h>

#include<algorithm>

#define ll long long

#define ln(x,y) (ll)(log(x)/log(y))

#define sqr(x) ((x)*(x))

using namespace std;

const char* fin="aP3.in";

const char* fout="aP3.out";

const ll inf=0x7fffffff;

const ll maxn=400007,maxm=maxn*4,maxk=22;

ll n,m,t,i,j,k,l,tot,limit,tmp,cnt;

ll fi[maxn],ne[maxm],la[maxm],de[maxn];

ll fa[maxn][maxk],sum[maxn][maxk],qsum[maxn][maxk];

ll dfn[maxn],low[maxn],num,stack[maxn],blg[maxn];

ll az[maxn];

ll ans;

bool bz[maxn],cz[maxn],dz[maxn];

ll read(){

    ll x=0;

    char ch=getchar();

    while (ch<'0' || ch>'9') ch=getchar();

    while (ch>='0' && ch<='9') x=x*10+ch-'0',ch=getchar();

    return x;

}

void add_line(ll a,ll b){

    tot++;

    ne[tot]=fi[a];

    la[tot]=b;

    fi[a]=tot;

}

void dfs(ll v,ll from){

    ll i,j,k;

    cz[v]=true;

    fa[v][0]=from;

    qsum[v][0]=sqr(sum[v][0]);

    de[v]=de[from]+1;

    for (i=1,j=ln(de[v],2);i<=j;i++){

        k=fa[v][i-1];

        fa[v][i]=fa[k][i-1];

        sum[v][i]=sum[v][i-1]+sum[k][i-1];

        qsum[v][i]=qsum[v][i-1]+qsum[k][i-1];

    }

    for (k=fi[v];k;k=ne[k]){

        if (!cz[az[blg[la[k]]]]){

            dfs(az[blg[la[k]]],v);

        }

    }

}

void up(ll &a,ll i,ll &j,ll &k){

    j+=sum[a][i];

    k+=qsum[a][i];

    a=fa[a][i];

}

ll lca(ll a,ll b){

    ll i,j=0,k=0;

    if (de[a]<de[b]) swap(a,b);

    for (i=ln(de[a]-de[b],2);i>=0;i--) if (de[fa[a][i]]>de[b]) up(a,i,j,k);

    if (de[a]!=de[b]) up(a,0,j,k);

    for (i=ln(de[a],2);i>=0;i--) if (fa[a][i]!=fa[b][i]) up(a,i,j,k),up(b,i,j,k);

    if (a!=b) up(a,0,j,k),up(b,0,j,k);

    j+=sum[a][0];

    k+=qsum[a][0];

    return sqr(j)-k;

}

void tarjan(ll v,ll from){

    ll i,j,k;

    dfn[v]=low[v]=++num;

    bz[j=stack[++stack[0]]=v]=true;

    for (k=fi[v];k;k=ne[k])

        if (!dz[(k+1)/2]){

            dz[(k+1)/2]=true;

            if (!dfn[la[k]]){

                tarjan(la[k],v);

                low[v]=min(low[la[k]],low[v]);

            }else if (bz[la[k]]) low[v]=min(low[v],dfn[la[k]]);

        }

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

        while (stack[stack[0]]!=j){

            blg[stack[stack[0]]]=v;

            bz[stack[stack[0]--]]=false;

        }

        blg[stack[stack[0]]]=v;

        bz[stack[stack[0]--]]=false;

    }

}

int main(){

    cnt=n=read();m=read();t=read();

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

        j=read();k=read();

        add_line(j,k);

        add_line(k,j);

    }

    tarjan(1,0);

    for (i=1;i<=n;i++){

        if (!az[blg[i]]) az[blg[i]]=++cnt;

        sum[az[blg[i]]][0]++;

        for (k=fi[i];k;k=ne[k]) add_line(az[blg[i]],la[k]);

    }

    dfs(n+1,0);

    for (i=1;i<=t;i++){

        j=read();

        k=read();

        ans+=lca(az[blg[j]],az[blg[k]]);

    }

    printf("%lld\n",ans);

    return 0;

}

启发

边双连通分量在某种程度上等同于强连通分量。