LCA 倍增（最近公共祖先）
图算法 · 倍增跳表 · 家谱的交汇处
家谱往上翻，翻到第一个共同祖先
树上两点的最近公共祖先（Lowest Common Ancestor）：同时是两点祖先、且深度最大的那个点——树上距离、路径查询全靠它。朴素做法让两点逐步爬父链，一次查询 O(n)；查询一多就顶不住。本页的树：
0
/ \
1 2
/ \ \
3 4 5
|
6
|
7倍增：跳 1 步、2 步、4 步的跳表
预处理 up[k][u] = u 往上跳 2^k 步的祖先，「爸爸的爸爸」递推：up[k][u] = up[k−1][up[k−1][u]]（跳 2^k = 先跳 2^(k−1) 再跳 2^(k−1)）。查询三段式：①深的先对齐——深度差按二进制拆成若干次跳；②相同即答案；③否则从高位试跳——祖先不同才跳（相同就跳可能越过 LCA），最后两点停在 LCA 的两个孩子上，父亲即答案。下表 8 行 × 4 列就是跳表，黄格是每一步引用的格子；右侧代码随步同步高亮。
| depth | up⁰ | up¹ | up² | |
|---|---|---|---|---|
| 0 | ||||
| 1 | ||||
| 2 | ||||
| 3 | ||||
| 4 | ||||
| 5 | ||||
| 6 | ||||
| 7 |
最近公共祖先（LCA）= 两点家谱的交汇处。朴素做法逐步爬父链 O(n)；倍增法先建「跳表」up[k][u]（u 往上跳 2^k 步的祖先），把一次查询压到 O(log n)。目标：LCA(7, 4) 与 LCA(6, 5)
为什么「祖先相同不能跳」
①对齐：深度差 d 按二进制拆解，第 k 位是 1 就沿
②试跳只认「不同」：
③收官：从高到低试完，两点恰好停在 LCA 的两个孩子上——
up^k 跳一次——O(log n) 步对齐。②试跳只认「不同」：
up[k][u] = up[k][v] 说明跳完已在公共祖先上—— 但可能不是最近的那个，跳了就回不了头；不同则说明还没到交汇处，放心双跳。③收官：从高到低试完，两点恰好停在 LCA 的两个孩子上——
up⁰ 一步即答案。 建表 O(n log n)、每次查询 O(log n)。最常用的衍生是树上距离：dist(u, v) = depth[u] + depth[v] − 2·depth[LCA]；离线批量查询可用 Tarjan 离线（并查集），链上重载场景还有树链剖分。与 换根 DP、树形 DP 一起，构成树上问题的三板斧。