upd：
2023.09.13 新建
非常好思路，学习自 Alex_Wei。
摘要
使用 st 表维护区间内所有点的 dfn 最小的父节点。
优点是好写、时间空间常数小。
前置约定
\(dfn_{i}\) ：\(i\) 是第几个被访问的点
\(sub_{i}\) ：以 \(i\) 为根的子树
\(LCA\) ：\(\text{LCA}(u,v)\)
原理
-
dfn 的性质： 设 \(dfn_{u}<dfn{v}\)， \(\forall dfn_{i} \in [dfn_{u},dfn_{v}] ,\ i\in sub_{Lca},\ i \ne \text{LCA}(u,v)\) ，即区间内 \(LCA\) 不出现，且任意一个节点都是 \(LCA\) 的子节点 。
-
由上述性质，易知 \([dfn_{u},dfn_{v}]\) 内至少有一个 \(LCA\) 的直接子节点。
-
设 \(u,v\) 无祖先关系，考虑维护 “区间内所有点的深度最小的父节点”，即为答案。
-
当 \(u\) 是 \(v\) 的祖先时，3. 不成立，发现仅需去掉 u 即可满足，并且在该情况下 3. 依然成立。所以查询的 \(dfn\) 区间改为 \([dfn_{u}+1,dfn_{v}]\) 。
-
发现在 4. 的情况下，\(LCA\) 一定是查询范围内 \(dfn\) 最小的点，所以可以从比较 \(dep\) 转化成比较 \(dfn\) 。
-
至此，问题变为区间可重的无修改查询，使用 st 表，预处理 \(O(n \log n)\) ，查询为 \(O(1)\) ，空间 \(O(n \log n)\)
-
当 \(u=v\) 时需要特判。
实现
void dfs(int u,int pa)
{
dfn[u]=++dc;//dc ： dfn_cnt
st[dc][0]=pa;
//…………………………………………………………
}
int get(int u,int v)
{
return ( dfn[u] < dfn[v] ) ? u : v ;
//传入父节点，返回 dfn 更小的父节点
}
void Pre()
{
for(int i=1;i<=__lg(n);i++)
for(int j=1;j+(1<<i)-1<=n;j++)
st[j][i] = get( st[ j ][i-1] , st[ j+(1<<(i-1)) ][i-1] );
}
int Lca(int u,int v)
{
if(u==v)return u;
if((u=dfn[u)>(v=dfn[v))swap(u,v);
int d=__lg(v-u);
return get( st[ u+1 ][d] , st[ v-(1<<d)+1 ][d] );
}