最近公共祖先

从 $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 in a rooted tree · Parent and depth in a tree在树中选定根后，由唯一根路径定义父子、祖先、深度与子树。提供定义和唯一性。LCA 可用于树上距离：

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

对一次只含 $k$ 个终点的查询，虚树构造理路虚树构造与终点路径压缩Virtual tree construction · Compressed terminal tree · 虚树将查询终点按DFS序排序，补相邻LCA并以栈连接最近保留祖先，在至多2k−1点的压缩树上计算连通子树与两两距离总和。按DFS序排列终点，只添加相邻终点的LCA，再连接最近的保留祖先。当 $k\ge 1$ 时保留点至多 $2k-1$ 个；虚边存整段原路径长度，可按两侧终点数计算距离总和。空集合和单终点分别输出空树和单点，不自动加入原根。

在FRT随机树嵌入理路FRT 随机树嵌入FRT tree embedding · Fakcharoenphol–Rao–Talwar embedding · Probabilistic tree embedding · 随机度量树嵌入将有限度量随机嵌入逐点对不收缩的层级树，以跨尺度区间记账证明每个固定点对的期望伸长为 O(log n)。的标签差边权约定下，叶标零、父子边长为(Γ父−Γ子)/2；两条到LCA的路径分别望远镜求和，叶距离恰为LCA标签Γ。查询仍在一棵固定树上进行，随机性属于建树阶段；每点对期望伸长的证明不能由一次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 的双向线性归约。说明两类静态查询可在线性规模下互相归约。这种等价针对静态查询问题的线性规模互归约，并保留相应的渐近预处理与查询能力；树与数组各自保留原有的数据表示。