前言
在这篇博客中，有欧拉序ST表实现 \(O(1)\) 查询 LCA 的算法，但在这篇知乎文章中，题主用 dfs序 实现了对比 欧拉序 常数更优的方法。
在这里，我们先约定 \(dfn_i\) 表示节点\(i\)第一次被访问顺序编号，\(out_i\) 表示以 \(i\) 为顶点的子树中最大的 \(dfn_j\)。
思考
观察 DFS序 的性质得到对于任意两个节点 u 和 v，若 \(dfn_u < dfn_v\)，如果 \(u\) 是 \(v\) 的祖先，那么 \(lca(u, v) = u\)，否则 \(lca(u, v)\) 就为区间 \([dfn_u, dfn_v]\) 中深度最小的节点的父节点，这是显然的。
AI给出的证明：
设 \(p = LCA(u, v)\)。
-
因为 \(u\) 不是 \(v\) 的祖先，\(u\) 和 \(v\) 位于 \(p\) 的不同子树中。
-
设 \(u\) 在 \(p\) 的子节点 \(C_i\) 的子树中，\(v\) 在 \(p\) 的子节点 \(C_j\) 的子树中。由于 \(dfn[u] < dfn[v]\)，根据 DFS 顺序，必有 \(i < j\)。
-
因此，DFS 序区间 \([dfn[u], dfn[v]]\) 必然完整包含 \(p\) 的子节点 \(C_{i+1}\) 的第一个被访问的节点。
-
区间内所有节点都是 \(p\) 的后代，且 \(p\) 本身不在该区间内（因为 \(p\) 在 \(dfn[u]\) 前已被访问）。所以区间内任意节点 \(x\) 的深度都满足 \(dep[x] \ge dep[p] + 1\)。
-
由第 3 步可知，区间内存在深度恰好为 \(dep[p] + 1\) 的节点（即 \(C_{i+1}\) 的第一个节点）。
-
综上，区间 \([dfn[u], dfn[v]]\) 中深度最小的节点 \(x = RMQ(dfn[u], dfn[v])\)，其深度必为 \(dep[p] + 1\)，即 \(x\) 是 \(p\) 的直接子节点。
-
所以 \(parent(x) = p = LCA(u, v)\)，即 \(LCA(u, v) = parent(RMQ(dfn[u], dfn[v]))\)。
那么实现同样是简单的，运用任意解决 RMQ 问题的数据结构（e.g., ST表）能在 \(O(1)\) 查询区间 \([dfn_u, dfn_v]\) 中深度最小的节点的父节点就可以做到 \(O(1)\) 查询 \(LCA\) 了。
代码实现
先鸽一下，欢迎 PR。