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)
1function lca(n: number, fa: number[], LOG: number, u: number, v: number): number {
2 const depth = new Array(n).fill(0); // 建表：depth + up[0] = fa
3 const up = [fa.slice()];
4 for (let i = 1; i < n; i++) depth[i] = depth[fa[i]] + 1;
5 for (let k = 1; k < LOG; k++) // 爸爸的爸爸
6 up.push(up[k - 1].map((p) => (p < 0 ? -1 : up[k - 1][p])));
7 if (depth[u] < depth[v]) [u, v] = [v, u];
8 for (let k = LOG - 1; k >= 0; k--) // ① 对齐：深度差按二进制拆跳
9 if ((depth[u] - depth[v]) & (1 << k)) u = up[k][u];
10 if (u === v) return u;
11 for (let k = LOG - 1; k >= 0; k--)
12 if (up[k][u] !== up[k][v]) { // ② 试跳：祖先不同才跳
13 u = up[k][u];
14 v = up[k][v];
15 }
16 return up[0][u]; // ③ 停在两孩子，父即答案
17}
树0 根；1,2 子；3,4 为 1 的子；5 为 2 的子；6 为 3 的子；7 为 6 的子
目标LCA(7, 4) 与 LCA(6, 5)
1 / 11
为什么「祖先相同不能跳」
①对齐：深度差 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 一起，构成树上问题的三板斧。