首先建出来以 $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;
}