倍增法（Binary Lifting）通过预处理每个节点的 2^k 级祖先，实现 O(log n) 查询任意两节点的最近公共祖先（LCA），是树上查询的基础工具。
一、LCA 问题
Mermaid · 渲染中（下方为源码）
graph TD A["预处理 2ᵏ 祖先"] --> B["O(log n) 查询 LCA"] B --> C["两节点跳到同层"] C --> D["二分跳找分叉点"]
给定有根树，多次查询两个节点 u, v 的最近公共祖先。
1
/ \
2 3
/ \
4 5
LCA(4, 5) = 2
LCA(4, 3) = 1
二、倍增预处理
up[u][k] = 节点 u 的第 2^k 级祖先
int LOG = 20; // 2^20 > 10^6
int[][] up; // up[n][LOG]
int[] depth;
void preprocess(int root, List<Integer>[] adj) {
int n = adj.length;
up = new int[n][LOG];
depth = new int[n];
dfs(root, 0, adj);
}
void dfs(int u, int parent, List<Integer>[] adj) {
up[u][0] = parent;
for (int k = 1; k < LOG; k++) {
up[u][k] = up[up[u][k - 1]][k - 1]; // 2^k = 2^(k-1) + 2^(k-1)
}
for (int v : adj[u]) {
if (v == parent) continue;
depth[v] = depth[u] + 1;
dfs(v, u, adj);
}
}