[APIO2018]铁人两项 [圆方树模板]

把这个图缩成圆方树，把方点的权值设成-1，圆点的权值设成点双的size，算 经过这个点的路径的数量*这个点的点权 的和即是答案。

#include <iostream>

#include <cstdio>

#include <cstring>

using namespace std;

const int N=;

struct Edge{

    int to[N],nxt[N],head[N],ecnt;

    Edge(){ecnt=;}

    void add(int bg,int ed) {nxt[++ecnt]=head[bg];to[ecnt]=ed;head[bg]=ecnt;}

    void ins() {int bg,ed;scanf("%d%d",&bg,&ed);add(bg,ed),add(ed,bg);}

}e1,e2;

int n,m,low[N],dfn[N],tim,stk[N],top,siz[N],tot,val[N],sum;

long long ans;

bool vis[N];

void tarjan(int x) {siz[x]=;

    low[x]=dfn[x]=++tim;vis[x]=;stk[++top]=x;

    for(int i=e1.head[x];i;i=e1.nxt[i]) {

        int v=e1.to[i];

        if(!dfn[v]) {

            tarjan(v);

            low[x]=min(low[x],low[v]);

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

                int u=,num=;

                ++tot;

                low[x]=min(low[x],low[v]);

                do {

                    u=stk[top--];num++;

                    e2.add(tot,u),e2.add(u,tot);

                    siz[tot]+=siz[u];

                }while(u!=v);

                val[tot]=num;siz[x]+=siz[tot];

                e2.add(tot,x),e2.add(x,tot);

            }

        }

        else  low[x]=min(low[x],dfn[v]);

    }

}

void dfs(int x,int fa) {

    int tmp=x<=n;

    ans+=2ll*siz[x]*(sum-siz[x])*val[x];

    for(int i=e2.head[x];i;i=e2.nxt[i]) {

        int v=e2.to[i];

        if(v!=fa) ans+=2ll*tmp*siz[v]*val[x],

        tmp+=siz[v],

        dfs(v,x);

    }

}

int main() {

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

    memset(val,-,sizeof val);

    for(int i=;i<=m;i++) e1.ins();

    for(int i=;i<=n;i++) if(!dfn[i]) tarjan(i),sum=siz[i],dfs(i,);

    printf("%lld",ans);

}

铁人两项