形式陈述

在根树中，节点 $u,v$ 的最近公共祖先 $\mathrm{LCA}(u,v)$ 是深度最大的公共祖先。 二进制倍增算法先把较深节点提升到相同深度，再从最高位向下同时提升两节点，保持它们祖先不同，最终返回共同父节点。预处理 $O(n\log n)$，单次查询 $O(\log n)$。

直觉

先消除深度差，再用由大到小的跳跃寻找“仍未相遇”的最高位置，最后一步即落到最近交点。

例子与边界

若一个节点是另一个节点的祖先，提升深度后两者立即相等。LCA 依赖选定根；同一无根树换根后答案可以改变。

推论与应用

用于树上距离、路径聚合、虚树、动态规划和层次关系查询。

参考资料

• OI-Wiki contributors, OI-Wiki (2026), LCA and binary lifting.
• cp-algorithms contributors, Algorithms for Competitive Programming (2026), lowest common ancestor.