P4630 [APIO2018] Duathlon 铁人两项

思路

圆方树，一个点双中的所有点都可以被经过，所以给圆点赋值-1，方点赋值为圆点个数，统计圆点两两之间的路径权值和即可

代码

#include <cstdio>

#include <algorithm>

#include <cstring>

#include <stack>

using namespace std;

int v2[100100*4],fir2[100100*2],nxt2[100100*4],cnt2;

void addedge2(int ui,int vi){

    ++cnt2;

    v2[cnt2]=vi;

    nxt2[cnt2]=fir2[ui];

    fir2[ui]=cnt2;

}

int v[100100*4],fir[100100*2],nxt[100100*4],cnt;

void addedge(int ui,int vi){

    ++cnt;

    v[cnt]=vi;

    nxt[cnt]=fir[ui];

    fir[ui]=cnt;

}

int fd_cnt,dfn[100100*2],low[100100*2],w_p[100100*2],dfs_clock;

int S[100100*2],topx=0,n,m,num;

void dfs(int u){

    low[u]=dfn[u]=++dfs_clock;

    S[++topx]=u;

    num++;

    for(int i=fir[u];i;i=nxt[i]){

        if(!dfn[v[i]]){

            dfs(v[i]);

            low[u]=min(low[u],low[v[i]]);

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

                ++fd_cnt;

                w_p[fd_cnt]=0;

                for(int x=0;x!=v[i];topx--){

                    x=S[topx];

                    addedge2(fd_cnt,x);

                    addedge2(x,fd_cnt);

                    ++w_p[fd_cnt];

                }

                addedge2(u,fd_cnt);

                addedge2(fd_cnt,u);

                ++w_p[fd_cnt];

            }

        }

        else

            low[u]=min(low[u],dfn[v[i]]);

    }

}

int sz[100100*2];

long long ans;

void dfs(int u,int f){

    sz[u]=(u<=n);

    for(int i=fir2[u];i;i=nxt2[i]){

        if(v2[i]==f)

            continue;

        dfs(v2[i],u);

        ans+=2LL*w_p[u]*sz[u]*sz[v2[i]];

        sz[u]+=sz[v2[i]];

    }

    ans+=2LL*w_p[u]*sz[u]*(num-sz[u]);

}

int main(){

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

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

        w_p[i]=-1;

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

        int a,b;

        scanf("%d %d",&a,&b);

        addedge(a,b);

        addedge(b,a);

    }

    fd_cnt=n;

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

        if(!dfn[i]){

            num=0;

            dfs(i);

            topx--;

            dfs(i,0);

        }

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

    return 0;

}