以下设 $dfn_u < dfn_v$。
结论
- $u = v$ 时：$u$ 为 LCA。
- $u \neq v$ 时：LCA 为 dfs 序上 $[dfn_u + 1, dfn_v]$ 区间内深度最小的点的父亲。
ST 表维护，预处理 $O(n\log n)$，查询 $O(1)$。
证明
$u = v$ 时显然。
$u \neq v$ 时：记 LCA 到 $v$ 路径上的儿子为 $x$。
- $u$ 不为 $v$ 的祖先：dfs 顺序大概是 $LCA \to u \to LCA \to x \to v$，所以 $dfn_x \in [dfn_u + 1, dfn_v]$。
- $u$ 为 $v$ 的祖先：此时 $u$ 即为 LCA，$u$ 的儿子也满足 $dfn_x \in [dfn_u + 1, dfn_v]$。
同时 $x$ 为 $u$ 到 $v$ 路径上除 LCA 外深度最小的点。
实现
实现上，可以直接在 ST 表的最底层记录父亲，比较时取 dfn 较小的结点。