【题解】[APIO2018] Duathlon 铁人两项 圆方树 luoguP4630 —Sai_0511

圆方树。
我们建立圆方树之后枚举每个起点和终点。
然后设方点的权值为点双的个数，圆点的权值是-1。
之后可以得到答案就是两点之间的点权和。

之后不难发现对于一个点的贡献可以用一遍 $\text{dfs}$得到, 这道题就做完了。

// luogu-judger-enable-o2
#include <bits/stdc++.h>
using namespace std;
const int maxn = 4e5 + 10;
typedef long long ll;
namespace Fast_Input {
    template<class T> inline void read(T& res) {
        res = 0;  char ch;  bool sign = 0;   
        do { ch = getchar();  sign |= ch == '-'; } while(!isdigit(ch));
        while(isdigit(ch)) res = (res << 1) + (res << 3) + (ch & 15),ch = getchar();
        (sign) && (res = -res);
        return;
    }
}
using Fast_Input::read;  
int n,m,i,j,k,sta_top,extra,tot,s;   
int dfn[maxn],low[maxn],sta[maxn],val[maxn],sz[maxn];
ll ans;  
struct Graph {
    int head[maxn],nxt[maxn << 1],ver[maxn << 1];   int ecnt;    
    inline Graph() { ecnt = 0;  memset(head,-1,sizeof(head)); }   
    inline void adde(int u,int v) {
        ver[++ecnt] = v;  nxt[ecnt] = head[u];
        head[u] = ecnt;  return;
    }
    inline void readd(int u,int v) {
        adde(u,v);  adde(v,u);  return;
    }
} gold,gnew;
inline void cmin(int& x,int y) {
    if(x > y) x = y;  return;
}
void tarjan(int u) {
    dfn[u] = ++tot;  low[u] = ++tot;  sta[++sta_top] = u;  sz[u] = 1;    
    for(int i = gold.head[u],v;~i;i = gold.nxt[i]) {
        v = gold.ver[i];  
        if(!dfn[v]) {
            tarjan(v);  cmin(low[u],low[v]); 
            if(low[v] >= dfn[u]) {
                int t = 0,cnt = 1;  extra++;
                do {
                    t = sta[sta_top--];  cnt++;  
                    gnew.readd(extra,t);
                    sz[extra] += sz[t];
                } while(t != v);  
                val[extra] = cnt;  sz[u] += sz[extra];  
                gnew.readd(extra,u); 
            }
        } else cmin(low[u],dfn[v]);   
    }
}
void dfs(int u,int fa) {
    int x = u <= n;   ans += 2ll * sz[u] * (s - sz[u]) * val[u];
    for(int i = gnew.head[u],v;~i;i = gnew.nxt[i]) {
        v = gnew.ver[i];  if(v == fa) continue;
        ans += 2ll * x * sz[v] * val[u];
        x += sz[v];  dfs(v,u);  
    }
    return;
}
int main() {
    read(n);  read(m);  extra = n;
    for(int i = 1;i <= n;i++) val[i] = -1;
    for(int i = 1,u,v;i <= m;i++) {
        read(u);  read(v);  
        gold.readd(u,v);
    } 
    for(int i = 1;i <= n;i++) {
        if(!dfn[i]) {
            tarjan(i); s = sz[i];  dfs(i,-1);   
        }
    }
    printf("%lld\n",ans);
}