学点分树，发现不会询问复杂度 \(O(1)\) 的 LCA。于是被迫递归式学习。
我们设 \(dfn_i\) 表示点 \(i\) 在 dfs 过程中第几个被访问到，把点按访问到的顺序排序得到的序列叫 dfs 序。
考虑 \(u\) 和 \(v\) 在 dfs 序上的位置之间的这一段序列有什么。
设 \(lca(u,v)=x,dfn_u<dfn_v\)。那么 \(x\) 到 \(v\) 路径上第一个点（即 \(v\) 所在的 \(x\) 的子树）一定在 \(u\) 和 \(v\) 之间。
而这个点就是 \(u\) 到 \(v\) 之间深度最小的点。\(lca(u,v)\) 就是 \(u\) 到 \(v\) 深度最小的点的父亲。
区间深度最小值用 ST 表维护。注意到 \(u\) 是 \(v\) 的祖先时深度最小的点会变成 \(u\)，我们改为在 \([dfn_u+1,dfn_v]\) 的区间上查询。
代码封装了一下。
struct LCA
{
int dfn[N],tot,dep[N],st[20][N];
il int get(int x,int y) {return dep[x]<dep[y]?x:y;}
void dfs(int u,int fa)
{
dfn[u]=++tot,st[0][tot]=fa; dep[u]=dep[fa]+1;
for(int i=head[u];i;i=e[i].nxt) if(e[i].to!=fa) dfs(e[i].to,u);
}
il void init()
{
dfs(rt,0);
for(int i=1;(1<<i)<=n;i++)
for(int j=1;j<=n-(1<<i)+1;j++)
st[i][j]=get(st[i-1][j],st[i-1][j+(1<<i-1)]);
}
il int lca(int x,int y)
{
if(x==y) return x;
if((x=dfn[x])>(y=dfn[y])) swap(x,y);
int l=__lg(y-x);
return get(st[l][x+1],st[l][y-(1<<l)+1]);
}
}l;