最近公共祖先

从 $u$ 与 $v$ 各自沿父亲链向根移动，两条链最终汇合；第一次汇合的位置就是 LCA。树的唯一根路径保证汇合后不会再次分叉，因此答案唯一。

定义本身只需要祖先偏序。二进制倍增、Euler Tour、RMQ 微块和 Tarjan 离线算法是不同实现，不应塞进 LCA 的定义。先固定问题对象，再比较预处理时间、查询时间、空间和在线性，才能避免把一种实现误当成概念本身。

若根为 $1$，$2,3$ 是其孩子，$4,5$ 是 $2$ 的孩子，则

若 $u$ 本身是 $v$ 的祖先，则

常见接口允许 $u=v$，此时答案就是 $u$。

LCA 依赖根。对路径 $1-2-3$，以 $1$ 为根时 $\mathrm{LCA}(2,3)=2$；以 $3$ 为根时答案变为 $3$。若输入是一般 DAG，两个节点可能存在多个互不比较的最低公共祖先；树上的唯一性证明不再适用。

动态链接或切断树边会使父亲、深度与祖先关系整体变化，静态预处理表可能失效。所谓“换根查询”也应区分：是永久改变根，还是用固定预处理回答假想根下的 LCA。

有根树与祖先关系公理库有根树与祖先关系Rooted tree · Ancestor relation · Parent and depth in a tree在树中选定根后，由唯一根路径定义父子、祖先、深度与子树。提供定义和唯一性。LCA 可用于树上距离：

它还支撑路径聚合、虚树、层级权限、系统发育树和树上差分。

常用实现包括：

• 二进制倍增公理库二进制倍增Binary lifting · Doubling technique预计算函数的 $2^k$ 次迭代，用输入步数的二进制展开快速跳转。：通常 $O(n\log n)$ 预处理、$O(\log n)$ 查询；
• Euler Tour 加RMQ公理库静态区间最值查询（RMQ）Range minimum query · RMQ预处理静态数组后，返回区间最小元素的位置并固定并列规则。：把首次出现区间中的最小深度位置还原为 LCA；
• 常数时间 RMQ公理库线性预处理常数时间 RMQConstant-time RMQ · Farach-Colton–Bender RMQ · 线性 RMQ将一般静态 RMQ 归约为深度差为正负一的数组，再用微块类型查表与宏块稀疏表实现线性预处理、常数查询。：可把静态查询降到 $O(1)$，同时保持线性级预处理与空间；
• 离线并查集方法：适合查询全部预先给出的场景。

RMQ–LCA 等价公理库RMQ 与 LCA 的等价归约RMQ-LCA equivalence · RMQ to LCA reduction用 Euler 深度序列与 Cartesian tree 建立静态 RMQ 和 LCA 的双向线性归约。说明两类静态查询可在线性规模下互相归约。这里的 equivalent_to 指问题级互归约与渐近数据结构能力，不表示一棵树和一个数组是同一种数学对象。