树上两个节点最近的共同祖先——朴素做法每次查询要 O(n)，倍增思想能把它压缩到 O(log n)。
给定一棵有根树，最近公共祖先（Lowest Common Ancestor，简称 LCA）指的是：给定两个节点 u、v，同时是它们祖先（包括自身）的节点里，深度最大的那一个。
最直接的做法：把 u、v 中较深的那个先向上跳到和另一个同样的深度，然后两个节点一步一步同时往上跳，直到两者相遇，相遇的位置就是 LCA。这个朴素做法每次查询最坏要跳 O(n) 步——如果需要回答很多次 LCA 查询，会很慢。树上倍增能把每次查询优化到 O(log n)。
倍增的核心是预处理一个数组 up[u][k]，表示节点 u 向上跳 2^k 步能到达的祖先。这个数组可以递推算出：up[u][k] = up[ up[u][k-1] ][k-1]——"跳 2^k 步"等于"先跳 2^(k-1) 步，再跳 2^(k-1) 步"。有了这张表，任何"向上跳 x 步"都能拆成若干个 2 的次方之和（二进制拆分），用倍增表拼出来，只需要 O(log n) 次跳跃。
| 步骤 | 做什么 |
|---|---|
| ① 预处理 | DFS 一遍树，算出每个节点的深度 depth[u] 和直接父亲 up[u][0]；再递推出 up[u][k]（k=1,2,3...） |
| ② 对齐深度 | 查询 LCA(u,v) 时，先把较深的那个节点向上跳，跳到和另一个节点同样的深度 |
| ③ 同时倍增上跳 | 从大到小枚举 k，如果 u、v 跳 2^k 步之后仍然不同，就把两者都跳上去（保证不会跳过 LCA） |
| ④ 收尾 | 循环结束后，u、v 的直接父亲就是 LCA |
用一棵 7 个节点的树演示，节点旁边标出深度：
| u | up[u][0]（跳1步） | up[u][1]（跳2步） | up[u][2]（跳4步） |
|---|---|---|---|
| 4 | 2 | 1 | 0 |
| 6 | 3 | 1 | 0 |
| 7 | 4 | 2 | 0 |
查询 LCA(7, 6)：depth[7]=3，depth[6]=2，7 更深，先把 7 往上跳 1 步对齐深度：
| 步骤 | 操作 | 结果 |
|---|---|---|
| 对齐深度 | 7 跳 2⁰=1 步：7 → up[7][0] = 4 | u=4, v=6（同深度 2） |
| k=2（跳4步） | up[4][2]=0 与 up[6][2]=0 相同 | 不跳（跳了会越过 LCA） |
| k=1（跳2步） | up[4][1]=1 与 up[6][1]=1 相同 | 不跳 |
| k=0（跳1步） | up[4][0]=2 与 up[6][0]=3 不同 | 都跳：u=2, v=3 |
| 循环结束，u、v 已经是兄弟节点，答案 = up[2][0] = 1 | ||
LCA(7,6)=1——验证一下：7 的祖先链是 7→4→2→1，6 的祖先链是 6→3→1，两条链唯一的公共节点就是 1，符合预期。k=2、k=1 时之所以"相同就不跳"，是因为如果这时候跳了，u、v 可能会一路跳到 LCA 的上面，跳过了真正的答案——只有在"跳了之后依然不同"时才安全地跳，这样循环结束时，u、v 一定是 LCA 的两个直接孩子（或者其中一个就是原来的 u/v，另一种边界情况见 ⑤）。| 1 | const int LOG = 20; // 2^20 远大于常见的节点数，足够用 |
| 2 | vector<int> children[MAXN]; |
| 3 | int up[MAXN][LOG], depth[MAXN]; |
| 4 | |
| 5 | void DFS(int u, int par) |
| 6 | { |
| 7 | up[u][0] = par; |
| 8 | for (int k = 1; k < LOG; k++) |
| 9 | up[u][k] = up[ up[u][k-1] ][k-1]; // ★ 跳 2^k 步 = 先跳 2^(k-1)，再跳 2^(k-1) |
| 10 | for (int v : children[u]) |
| 11 | { |
| 12 | depth[v] = depth[u] + 1; |
| 13 | DFS(v, u); |
| 14 | } |
| 15 | } |
| 16 | |
| 17 | int LCA(int u, int v) |
| 18 | { |
| 19 | if (depth[u] < depth[v]) swap(u, v); // 保证 u 更深（或一样深） |
| 20 | int diff = depth[u] - depth[v]; |
| 21 | for (int k = 0; k < LOG; k++) |
| 22 | if (diff >> k & 1) u = up[u][k]; // ★ 把深度差 diff 按二进制拆分，跳到同一深度 |
| 23 | if (u == v) return u; // 对齐后 u、v 重合，说明 v 本来就是 u 的祖先 |
| 24 | |
| 25 | for (int k = LOG - 1; k >= 0; k--) // ★ 从大到小尝试跳，跳了之后不同才跳 |
| 26 | if (up[u][k] != up[v][k]) |
| 27 | { |
| 28 | u = up[u][k]; |
| 29 | v = up[v][k]; |
| 30 | } |
| 31 | return up[u][0]; // 循环结束，u、v 是 LCA 的两个孩子，它们的父亲就是答案 |
| 32 | } |
diff=5（二进制 101），需要跳 5 步，会先判断第 0 位是 1（跳 2⁰=1 步），第 2 位是 1（跳 2²=4 步），总共跳了 1+4=5 步——用倍增表拼出任意步数，只需要 O(log n) 次跳跃，而不是跳 5 次单步。第 25～30 行"两个指针同时倍增"用的是同样的思路，只是判断条件从"深度差的某一位是不是 1"变成了"跳了之后 u、v 还相不相同"。预处理 up 数组需要 O(n log n)（每个节点算 log n 个倍增值）；每次查询只需要 O(log n)（对齐深度、同步跳跃各一次 log n 循环）。
if (u == v) return u; 是必要的——对齐深度之后，如果两个节点已经重合，说明较浅的那个节点本来就是较深节点的祖先，直接返回即可，不需要再进入下面"同时跳跃"的循环（那个循环假设 u ≠ v，如果不加这个判断，跳跃过程可能会得出错误的结果或者浪费计算）。LOG 开得不够大：LOG 需要满足 2^LOG ≥ n（节点数），如果开小了，深度差较大的两个节点没法通过二进制拆分完全对齐深度，跳跃会出错。竞赛中通常直接取一个足够大的固定值（比如 20，对应节点数上限约 100 万），不需要精确计算。up 数组和 depth 数组只依赖树的结构本身，和具体查询哪两个节点无关——只需要在处理所有查询之前，对树做一次 DFS 预处理，之后的每次 LCA 查询都直接复用这份预处理结果，不需要也不应该每次查询都重新 DFS 一遍。