最小公共祖先（LCA）问题的倍增算法

题目描述
最小公共祖先（Lowest Common Ancestor, LCA）问题要求找出有根树中两个节点的最近公共祖先节点。例如，在树结构中，节点 \(u\) 和 \(v\) 的公共祖先中深度最大的节点即为它们的 LCA。该问题在树上的路径查询、网络路由优化等领域有广泛应用。倍增算法通过预处理树结构，支持每次查询在 \(O(\log n)\) 时间内完成，适用于多次查询的场景。

解题过程

1. 问题分析

假设树有 \(n\) 个节点，根节点为 \(r\)。对于任意节点 \(u\) 和 \(v\)，求 LCA 的朴素方法是：

1. 从 \(u\) 和 \(v\) 分别向上跳到根节点，记录路径上的所有祖先。
2. 比较两条路径，最后一个相同的节点即为 LCA。
   但这种方法每次查询的时间复杂度为 \(O(n)\)，在多次查询时效率低下。倍增算法的核心思想是通过预处理存储每个节点的 \(2^k\) 级祖先，将单次查询的跳跃次数优化到 \(O(\log n)\)。

2. 预处理阶段

步骤 1：初始化数据结构

• 定义数组 depth[] 存储每个节点的深度（根节点深度为 0）。
• 定义数组 parent[k][u] 表示节点 \(u\) 的 \(2^k\) 级祖先（即向上跳 \(2^k\) 步到达的节点）。若不存在则为 -1。

步骤 2：DFS 遍历树

通过深度优先搜索（DFS）计算每个节点的深度和直接父节点（即 parent[0][u]）：

def dfs(u, p, d):
    depth[u] = d
    parent[0][u] = p
    for v in tree[u]:
        if v != p:
            dfs(v, u, d + 1)

初始化调用：dfs(root, -1, 0)。

步骤 3：填充倍增表

利用动态规划填充 parent[k][u]：

\[\text{parent}[k][u] = \text{parent}[k-1][\text{parent}[k-1][u]] \]

即节点 \(u\) 的 \(2^k\) 级祖先等于其 \(2^{k-1}\) 级祖先的 \(2^{k-1}\) 级祖先。

max_log = math.ceil(math.log2(n))  # 最大跳跃步数对数
for k in range(1, max_log + 1):
    for u in range(n):
        if parent[k-1][u] != -1:
            parent[k][u] = parent[k-1][parent[k-1][u]]
        else:
            parent[k][u] = -1

3. 查询阶段

给定节点 \(u\) 和 \(v\)，求 LCA 的步骤如下：

步骤 1：调整到同一深度

若 depth[u] < depth[v]，交换 \(u\) 和 \(v\) 确保 \(u\) 深度较大。将 \(u\) 向上跳至与 \(v\) 同一深度：

def lift(u, d):  # 将 u 向上跳 d 步
    k = 0
    while d > 0:
        if d & 1:  # 二进制分解
            u = parent[k][u]
        d //= 2
        k += 1
    return u

更高效的方式是按二进制位从高位到低位跳跃：

diff = depth[u] - depth[v]
k = max_log
while k >= 0:
    if diff >= (1 << k):
        u = parent[k][u]
        diff -= (1 << k)
    k -= 1

步骤 2：同步向上跳跃

若此时 \(u = v\)，说明 \(v\) 是 \(u\) 的祖先，直接返回 \(v\)。否则，从最大步数 \(k = \max\_log\) 开始尝试：

• 若 parent[k][u] != parent[k][v]，说明跳跃 \(2^k\) 步后仍未到达公共祖先，此时同时向上跳：

\[ u = \text{parent}[k][u], \quad v = \text{parent}[k][v] \]

• 若相等，则说明跳过头了，不跳跃。
  最终 \(u\) 和 \(v\) 的直接父节点即为 LCA：

k = max_log
while k >= 0:
    if parent[k][u] != parent[k][v]:
        u = parent[k][u]
        v = parent[k][v]
    k -= 1
return parent[0][u]  # 或 parent[0][v]

4. 复杂度分析

• 预处理：DFS 遍历 \(O(n)\)，填充倍增表 \(O(n \log n)\)。
• 单次查询：\(O(\log n)\)。
• 总复杂度：\(O(n \log n + q \log n)\)（\(q\) 为查询次数）。

5. 示例验证

考虑树：

    0
   / \
  1   2
 / \   \
3   4   5

查询 LCA(3, 4)：

1. 深度相同（depth=2），但直接父节点不同。
2. 从 \(k=2\) 开始尝试（最大步数 4，但实际深度为 2，需调整 \(k\) 上限）。
3. 最终同步跳到节点 1，LCA 为 1。

总结
倍增算法通过预处理树的二进制跳跃信息，将 LCA 查询优化到对数时间，适用于需要高效处理大量查询的场景。关键点在于理解二进制跳跃的分解和动态规划填充祖先表。