核心概述
最近公共祖先（Lowest Common Ancestor, LCA）在树上求两点 u、v 的最近公共祖先，典型实现包括二进制提升与欧拉序+RMQ，预处理 O(N log N)，查询 O(log N)/O(1)。
原文引述
Description: Find the lowest common ancestor on a rooted tree. Supports binary lifting or Euler tour with RMQ. Time: Build O(N log N); Query O(log N) with lifting or O(1) with RMQ
展开阐述
定义与背景
- 问题：在根树或森林中，给定两个节点 u、v，返回同时为二者祖先的节点中离它们最近者。
- 典型适用：路径距离/路径分解、虚树构建、树上 DP 的分支合并、重链剖分/HLD 的配套能力等。
- 能力边界：LCA 在同一棵树内有意义；森林需分别处理或连虚根。
接口/字段/数据结构（据常见实现）
- 构造与建树
- LCA(n)：构造 n 节点结构；
- addEdge(u,v)：无向边建树；
- init(root=0)：以 root 为根预处理（可对每棵树分别调用）。
- 查询接口
- lca(u,v)：返回最近公共祖先；
- dist(u,v)：depth[u] + depth[v] − 2·depth[lca(u,v)]；
- jmp(u,k)：从 u 向上跳 k 步（越界返回 -1）。
- 必要数据
- depth[v]：深度；
- up[k][v]：2^k 祖先（倍增法），或
- euler、first[v]、深度数组 + RMQ 结构（欧拉 + RMQ）。
实现A：二进制提升（倍增）
- 预处理
- DFS 记录 depth[v] 与 up[0][v]=parent[v]；
- 对 k=1..LOG：up[k][v] = up[k-1][ up[k-1][v] ]。
- 查询 lca(u,v)
- 若 depth[u] < depth[v] 则交换；
- 将 u 向上跳 depth 差；
- 自大到小枚举 k：若 up[k][u] ≠ up[k][v]，则同时上跳；
- 返回 up[0][u]。
- 复杂度
- 预处理 O(N log N)；查询 O(log N)。
实现B：欧拉序 + RMQ
- 欧拉遍历
- 记录 DFS 过程中节点访问序列 e，以及每个节点首次出现位置 first[v]；
- 保存访问时的深度数组。
- RMQ
- LCA(u,v) 等价为 e 在 [first[u], first[v]] 范围内深度最小的节点；
- 用稀疏表/线段树预处理 RMQ：O(M log M)，M≈2N−1；查询 O(1)/O(log M)。
- 适用性
- 静态图，查询非常多时具有优势；亦便于配合离线流程。
- 依赖 011-数据结构-区间最值查询 的 RMQ 技术。
输出语义
- lca(u,v)：返回最近公共祖先；
- dist(u,v)：返回边数距离（加权树可在 DFS 中维护前缀权得加权距离）；
- jmp(u,k)：若不存在则返回 -1。
复杂度与边界条件
- 复杂度
- 倍增：预处理 O(N log N)，查询 O(log N)；
- 欧拉+RMQ：预处理 O(N log N)，查询 O(1)（稀疏表）。
- 边界与一致性
- 根选择仅影响 depth，不影响 LCA 正确性；
- 森林：对每棵树分别 init，或加虚根；
- up[k][root] 可置 -1 或 root，自洽即可；查询时注意越界保护。
变体/扩展与关系
- 与 066-图论-重链剖分：若需要路径聚合/修改，HLD 更合适，LCA 只是副产品；
- 与 069-图论-LinkCutTree：LCT 用于动态树，在线 link/cut 场景；静态树优先 LCA/倍增；
- 与 054-图论-二进制提升：倍增条目更细化了上跳与 LCA 的模板实现；
- 与欧拉+RMQ：查询极多且静态时选 RMQ，需路径分解或多类查询选 HLD。
正确性要点与不变式
- 祖先闭包不变式：up[k][v] 始终为 v 的祖先（或哨兵）；
- 深度对齐：上跳将较深节点抬至与另一点同深度，不会跨越 LCA；
- 分离原则：自高到低同步上跳时保持“尚未越过 LCA”的不变式，最终父即 LCA。
与相邻技术的对比与取舍建议
- 仅需求 LCA/距离：倍增/欧拉均可；
- 需求路径聚合：优先 066-图论-重链剖分；
- 动态连边/断边：选 069-图论-LinkCutTree；
- 虚树/多源路径：可配合 055-图论-虚树构建。