Binary Lifting：O(log n) 跳祖先、找 LCA

要從一個節點往上跳 100 步，不需要跳 100 次——二進制 100 = 64 + 32 + 4，三次就夠。

核心思路

up[v][j] 表示從節點 v 往上跳 2^j 步到達的祖先。

up[v][0] = v 的父節點
up[v][j] = up[up[v][j-1]][j-1]
           先跳 2^(j-1) 步，再跳 2^(j-1) 步 = 共跳 2^j 步

預處理 O(n log n)，之後任意「從 v 往上跳 k 步」只需 O(log n)：把 k 表示成二進制，對每個為 1 的 bit 跳一次。

預處理

static final int LOG = 18; // 2^18 > 10^5
int[][] up = new int[n][LOG];
 
void preprocess() {
    dfs(root, -1, 0); // 記錄 depth、parent
 
    for (int j = 1; j < LOG; j++)
        for (int v = 0; v < n; v++)
            if (up[v][j-1] != -1)
                up[v][j] = up[up[v][j-1]][j-1];
            else
                up[v][j] = -1; // 越界（超出根）
}

LCA（最近公共祖先）查詢

int lca(int u, int v) {
    // Step 1：讓較深的節點跳到和另一個同深度
    if (depth[u] < depth[v]) { int tmp = u; u = v; v = tmp; }
    int diff = depth[u] - depth[v];
    for (int j = 0; j < LOG; j++)
        if (((diff >> j) & 1) == 1)
            u = up[u][j];
 
    if (u == v) return u; // 深度對齊後相遇，LCA 就是這個節點
 
    // Step 2：兩個節點一起往上跳，保持「跳了還沒相遇」
    for (int j = LOG - 1; j >= 0; j--)
        if (up[u][j] != up[v][j]) {
            u = up[u][j];
            v = up[v][j];
        }
 
    return up[u][0]; // 再跳一步就是 LCA
}

路徑查詢的延伸

Binary Lifting 不只能跳，還能在跳的過程中查詢路徑上的最大值/最小值/和：

// 額外維護 maxVal[v][j] = v 往上跳 2^j 步路徑上的最大邊權
maxVal[v][j] = max(maxVal[v][j-1], maxVal[up[v][j-1]][j-1]);
 
// 查詢 u 到 LCA 路徑的最大邊權：在跳的過程中順帶收集

LCA 後的路徑長度 = depth[u] + depth[v] - 2 × depth[LCA(u,v)]。

應用場景

• LCA 查詢：競程最常見，幾乎所有樹上路徑問題的基礎
• 樹上路徑最大值/最小值：配合 sparse table 擴展
• 第 k 個祖先：直接應用，O(log n)
• Kruskal 重構樹：最小生成樹的邊權 LCA 查詢

---

Binary Lifting 的本質是空間換時間的 sparse table 思想——預處理 2 的冪次，讓任意步數的查詢變成二進制分解。