最近公共祖先 LCA (Lowest Common Ancestor)

📖 算法原理：倍增递推与对齐跳转定理

在有根树中，两个节点 $u$ 和 $v$ 的最近公共祖先 (LCA) 是指深度最大且同时是 $u$ 和 $v$ 祖先的节点。朴素的逐层向上查找复杂度为 $O(N)$，倍增算法通过翻倍跳跃可将单次查询优化至 $O(\log N)$。

📐 倍增跳跃表递推递推式

我们用 fa[u][j] 表示节点 $u$ 向上跳跃 $2^j$ 步到达的祖先。其核心状态转移方程为：

$fa[u][j] = fa[fa[u][j-1]][j-1]$

其物理意义为：向上跳跃 $2^j$ 步，等价于先向上跳跃 $2^{j-1}$ 步，再从该祖先向上跳跃 $2^{j-1}$ 步。（例如：向上跳 8 步等于先跳 4 步，再跳 4 步）。

📐 倍增求解 LCA 三步走战略

深度对齐 (Depth Alignment)：不妨设 $depth[u] \ge depth[v]$。我们通过二进制分解高度差 $D = depth[u] - depth[v]$，利用 $2^j$ 的步长将 $u$ 向上跳转对齐到与 $v$ 相同的深度。
同深度判断：若对齐后发现 $u == v$，说明 $v$ 本身就是 $u$ 的祖先，此时直接返回 $u$（即 LCA 寻找完毕）。
双端同步跳转 (Simultaneous Leaping)：若 $u \ne v$，我们从大到小枚举步长 $j = \lfloor \log N \rfloor \to 0$。如果 `fa[u][j] != fa[v][j]`，说明还没跳过头（若跳跃后重合，可能是 LCA，也可能是更上层的公共祖先；我们必须卡在刚好低于 LCA 的位置）。此时，我们同步让 $u = fa[u][j]$ 且 $v = fa[v][j]$。最终，它们刚好停留在 LCA 的下一层，返回 fa[u][0] 即为最终的 LCA！

已选节点： A: 8 , B: 11

演示速度：

在上方树图中直接点击任意两个不同的节点，然后点击"开始倍增 LCA"或"单步执行"查看动态跳转流程。

当前二进制指数 j (2^j 步长) -

节点 A (u) 深度及位置 A: 8 (depth: 4)

节点 B (v) 深度及位置 B: 11 (depth: 4)

🌲 LCA 倍增飞跃树状网络 (Lowest Common Ancestor Tree Playground)

初始节点 A (u)

初始节点 B (v)

跳转探索路径

锁定 LCA 节点

int getLCA(int u, int v) {
    if (depth[u] < depth[v]) swap(u, v); // 保证 u 深度大于等于 v
    
    // 第一阶段：利用倍增大步将 u 向上对齐到与 v 相同深度
    for (int i = 3; i >= 0; i--) {
        if (depth[u] - (1 << i) >= depth[v]) {
            u = fa[u][i]; 
        }
    }
    
    if (u == v) return u; // 如果对齐后重合，说明 v 就是 LCA
    
    // 第二阶段：u 和 v 深度相同，同步向上翻倍跳跃
    for (int i = 3; i >= 0; i--) {
        if (fa[u][i] != fa[v][i]) { // 如果跳完后祖先不同，说明还没跳过 LCA
            u = fa[u][i];
            v = fa[v][i];
        }
    }
    
    return fa[u][0]; // 此时 u, v 刚好在 LCA 下方，父节点即为 LCA
}

📋 LCA 倍增跳跃推导历史步骤