CodeChef GRAPHCNT

首先建出来以 $1$ 为根的支配树，然后 $1$ 到两个点的路径的最长重合部分就是他们在支配树上的LCA到根的链，答案就是求在支配树上LCA为 $1$ 的点对数量

这简直是200年没更博后首次更博了……你们对我是驴（雾

#include <iostream>
#include <cstdio>

#define MAX_N 100010
#define MAX_M 500010
#define inf 0x3f3f3f3f
typedef long long ll;

using std::cerr;
using std::endl;

struct Graph{
    int to[MAX_M], ne[MAX_M], head[MAX_N], cnt;
    int &operator [](int x){
        return head[x];
    }
    void add_edge(int x, int y){
        to[++cnt] = y, ne[cnt] = head[x], head[x] = cnt;
    }
}G, rG, T, W;

int N, M;

namespace DominatorTree{
    int dfn[MAX_N], a[MAX_N], idom[MAX_N], sdom[MAX_N], fa[MAX_N];
    namespace U{
        int fa[MAX_N], mn[MAX_N];
        int find(int x){
            if(fa[x] == x) return x;
            int tmp = fa[x];
            fa[x] = find(fa[x]);
            mn[x] = dfn[sdom[mn[x]]] < dfn[sdom[mn[tmp]]] ? mn[x] : mn[tmp];
            return fa[x];
        }
        int query(int x){
            find(x); return mn[x];
        }
    }
    void dfs(int x){
        dfn[x] = ++dfn[0], a[dfn[0]] = x;
        for(int i = G[x]; i; i = G.ne[i]) if(!dfn[G.to[i]]){
            fa[G.to[i]] = x;
            dfs(G.to[i]);
        }
    }
    void work(){
        dfs(1);
        for(int i = 1; i <= dfn[0]; i++)
            sdom[a[i]] = U::fa[a[i]] = U::mn[a[i]] = a[i];
        for(int t = dfn[0], mn, x; t >= 2; t--){
            mn = inf;
            x = a[t];
            for(int i = rG[x]; i; i = rG.ne[i])
                if(dfn[rG.to[i]] < t && dfn[rG.to[i]]) 
                    mn = std::min(mn, dfn[rG.to[i]]);
                else
                    mn = std::min(mn, dfn[sdom[U::query(rG.to[i])]]);
            sdom[x] = a[mn];
            W.add_edge(sdom[x], x);
            U::fa[x] = fa[x];
            for(int i = W[fa[x]]; i; i = W.ne[i]){
                x = W.to[i];
                if(sdom[x] == sdom[U::query(x)])
                    idom[x] = sdom[x];
                else
                    idom[x] = U::query(x);
            }
            W[fa[a[t]]] = 0;
        }
        for(int i = 2; i <= dfn[0]; i++){
            if(idom[a[i]] != sdom[a[i]])
                idom[a[i]] = idom[idom[a[i]]];
            T.add_edge(idom[a[i]], a[i]);
        }
    }
}

int sz[MAX_N];

void dfs(int x){
    sz[x] = 1;
    for(int i = T[x]; i; i = T.ne[i]){
        dfs(T.to[i]);
        sz[x] += sz[T.to[i]];
    }
}

int main(){
    scanf("%d%d", &N, &M);
    for(int i = 1, x, y; i <= M; i++){
        scanf("%d%d", &x, &y);
        G.add_edge(x, y);
        rG.add_edge(y, x);
    }
    DominatorTree::work();
    dfs(1);
    ll tmp = 1, ans = 0;
    for(int i = T[1]; i; i = T.ne[i])
        ans += tmp * sz[T.to[i]], tmp += sz[T.to[i]];
    printf("%lld\n", ans);
    return 0;
}