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

字数 3691 2025-12-14 13:39:27

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

题目描述

给定一棵有 \(n\) 个节点的树（无环连通无向图），并接收 \(m\) 次查询。每次查询会提供树中的两个节点 \(u\) 和 \(v\)，要求快速求出它们的最小公共祖先（Lowest Common Ancestor, LCA），即在树中同时作为 \(u\) 和 \(v\) 的祖先且深度最大的节点。要求预处理时间复杂度为 \(O(n \log n)\)，每次查询时间复杂度为 \(O(\log n)\)，整体高效处理大量查询。

例如，在一棵树中，若节点 \(u\) 和 \(v\) 的祖先都包括根节点和某个中间节点，那么其中深度最大的那个共同祖先就是 LCA。

解题过程

步骤 1：理解基本概念与朴素解法

首先，我们需要明确树的一些基本属性：

树中任意两个节点之间有且仅有一条简单路径。
如果指定一个根节点（通常设为节点 1），那么每个节点都有一个深度（depth），即从根到该节点的路径上的边数。根的深度为 0 或 1（通常设为 0 或 1，根据实现习惯，这里我们设根深度为 0）。
节点 \(a\) 是节点 \(b\) 的祖先，当且仅当 \(a\) 在从根到 \(b\) 的路径上。

一个朴素的 LCA 求解方法是：对于每次查询 \((u, v)\)：

将 \(u\) 和 \(v\) 向上移动到同一深度。例如，若 \(depth[u] > depth[v]\)，则将 \(u\) 向上移动 \(depth[u] - depth[v]\) 步到其父节点，直到两者深度相同。
然后同时将 \(u\) 和 \(v\) 向上移动，直到它们相遇，相遇的节点就是 LCA。

但是，每一步向上移动都需要 \(O(h)\) 的时间（其中 \(h\) 是树的高度），在最坏情况（如链状树）下，\(h = O(n)\)，导致每次查询 \(O(n)\)，总时间 \(O(nm)\) 不可接受。

步骤 2：引入倍增思想

为了加速向上移动的过程，我们可以使用倍增（Binary Lifting）技术。
其核心思想是：预先计算出每个节点向上跳 \(2^k\) 步所到达的祖先节点，其中 \(k = 0, 1, 2, \dots, \lfloor \log_2 n \rfloor\)。

定义：

\(parent[u][k]\) 表示节点 \(u\) 向上跳 \(2^k\) 步后到达的节点。如果跳 \(2^k\) 步后超过了根节点，则设为 -1 或 0（表示不存在）。
特别地，\(parent[u][0]\) 就是 \(u\) 的直接父节点（当 \(u\) 不是根时）。

这样，我们就可以利用这些预处理信息，在 \(O(\log n)\) 时间内完成任意大步长的向上跳跃。

步骤 3：预处理阶段

选择根节点：通常选择节点 1 作为根，进行深度优先搜索（DFS）或广度优先搜索（BFS），计算出每个节点的深度 \(depth[u]\) 和直接父节点 \(parent[u][0]\)。

伪代码（DFS）：
```
function dfs(u, p):
    parent[u][0] = p
    depth[u] = depth[p] + 1
    for each neighbor v of u:
        if v != p:
            dfs(v, u)
```
计算倍增表：
对于 \(k = 1\) 到 \(\lfloor \log_2 n \rfloor\)：
对于每个节点 \(u\)：
如果 \(parent[u][k-1]\) 存在（不为 -1）：
\(parent[u][k] = parent[ parent[u][k-1] ][k-1]\)
否则：
\(parent[u][k] = -1\)（表示不存在）

解释：要跳到 \(2^k\) 步，可以先跳 \(2^{k-1}\) 步到节点 \(parent[u][k-1]\)，再从那里跳 \(2^{k-1}\) 步。这利用了 \(2^{k-1} + 2^{k-1} = 2^k\)。

预处理时间复杂度：每个节点有 \(O(\log n)\) 个状态，总 \(O(n \log n)\)。

步骤 4：查询 LCA 的倍增算法

给定查询 \((u, v)\)：

调整深度：如果 \(depth[u] < depth[v]\)，交换 \(u\) 和 \(v\)，使得 \(u\) 是较深的节点。
然后，将 \(u\) 向上移动，直到与 \(v\) 深度相同。
具体操作：设差 \(d = depth[u] - depth[v]\)。将 \(d\) 表示为二进制，对于每个二进制位 \(k\)（从高到低），如果 \(d\) 的第 \(k\) 位为 1，就将 \(u\) 跳到 \(parent[u][k]\)。
例如，若 \(d = 5\)（二进制 101），则先跳 \(2^2 = 4\) 步，再跳 \(2^0 = 1\) 步。
如果此时 \(u == v\)，那么 LCA 就是 \(u\)（因为 \(v\) 是 \(u\) 的祖先）。
否则，同时向上跳：
从最大的 \(k = \lfloor \log_2 n \rfloor\) 开始向下尝试到 0：
如果 \(parent[u][k] != parent[v][k]\)（即跳 \(2^k\) 步后，两者仍不同）：
将 \(u\) 跳到 \(parent[u][k]\)，将 \(v\) 跳到 \(parent[v][k]\)。
这个循环结束时，\(u\) 和 \(v\) 会处于 LCA 的直接子节点位置（即它们再向上一步就是 LCA）。
返回 LCA：最后，\(parent[u][0]\)（或 \(parent[v][0]\)）就是 LCA。

查询时间复杂度：每次调整深度和同时向上跳都是 \(O(\log n)\)。

步骤 5：举例说明

假设树如下（以 1 为根）：

深度：depth[1]=0, depth[2]=1, depth[3]=1, depth[4]=2, depth[5]=2, depth[6]=2。

预处理 parent 表（只列部分）：

parent[2][0]=1, parent[2][1]=-1（因为跳 2^1=2 步超根）
parent[4][0]=2, parent[4][1]=1（因为 parent[4][1] = parent[ parent[4][0] ][0] = parent[2][0] = 1）

查询 LCA(4, 5)：

depth[4]=2, depth[5]=2，深度相同。
同时向上跳：最大 k=1（因为 n=6，log2(6)≈2，但实际只用到1）。
- k=1：parent[4][1]=1, parent[5][1]=? 先算 parent[5][0]=2, parent[5][1]=parent[2][0]=1。两者相等，所以不跳（因为我们要找最后一次跳后仍不同的情况）。
- k=0：parent[4][0]=2, parent[5][0]=2，相等，不跳。
  循环结束，此时 u=4, v=5。
返回 parent[u][0] = 2，即 LCA 是 2。

查询 LCA(4, 6)：

depth[4]=2, depth[6]=2，深度相同。
同时向上跳：
- k=1：parent[4][1]=1, parent[6][1]=? parent[6][0]=3, parent[6][1]=parent[3][0]=1。相等，不跳。
- k=0：parent[4][0]=2, parent[6][0]=3，不相等。所以 u 跳到 2，v 跳到 3。
  现在 u=2, v=3。
  继续 k=0：parent[2][0]=1, parent[3][0]=1，相等，不跳。
返回 parent[u][0] = 1，LCA 是 1。

步骤 6：算法总结

预处理：DFS 计算 depth 和 parent[u][0]，然后动态规划填充 parent[u][k] 表。
查询：通过二进制拆分快速调整深度，然后从大到小尝试跳跃，找到 LCA。
时间复杂度：预处理 \(O(n \log n)\)，查询 \(O(\log n)\)。
空间复杂度：\(O(n \log n)\) 存储 parent 表。

倍增算法是 LCA 问题的经典在线解法，高效且易于实现，广泛用于树上的路径查询问题。

寻找最小公共祖先（LCA）问题的倍增算法题目描述给定一棵有 \( n \) 个节点的树（无环连通无向图），并接收 \( m \) 次查询。每次查询会提供树中的两个节点 \( u \) 和 \( v \)，要求快速求出它们的最小公共祖先（Lowest Common Ancestor, LCA），即在树中同时作为 \( u \) 和 \( v \) 的祖先且深度最大的节点。要求预处理时间复杂度为 \( O(n \log n) \)，每次查询时间复杂度为 \( O(\log n) \)，整体高效处理大量查询。例如，在一棵树中，若节点 \( u \) 和 \( v \) 的祖先都包括根节点和某个中间节点，那么其中深度最大的那个共同祖先就是 LCA。解题过程步骤 1：理解基本概念与朴素解法首先，我们需要明确树的一些基本属性：树中任意两个节点之间有且仅有一条简单路径。如果指定一个根节点（通常设为节点 1），那么每个节点都有一个深度（depth），即从根到该节点的路径上的边数。根的深度为 0 或 1（通常设为 0 或 1，根据实现习惯，这里我们设根深度为 0）。节点 \( a \) 是节点 \( b \) 的祖先，当且仅当 \( a \) 在从根到 \( b \) 的路径上。一个朴素的 LCA 求解方法是：对于每次查询 \( (u, v) \)：将 \( u \) 和 \( v \) 向上移动到同一深度。例如，若 \( depth[ u] > depth[ v] \)，则将 \( u \) 向上移动 \( depth[ u] - depth[ v ] \) 步到其父节点，直到两者深度相同。然后同时将 \( u \) 和 \( v \) 向上移动，直到它们相遇，相遇的节点就是 LCA。但是，每一步向上移动都需要 \( O(h) \) 的时间（其中 \( h \) 是树的高度），在最坏情况（如链状树）下，\( h = O(n) \)，导致每次查询 \( O(n) \)，总时间 \( O(nm) \) 不可接受。步骤 2：引入倍增思想为了加速向上移动的过程，我们可以使用倍增（Binary Lifting）技术。其核心思想是：预先计算出每个节点向上跳 \( 2^k \) 步所到达的祖先节点，其中 \( k = 0, 1, 2, \dots, \lfloor \log_ 2 n \rfloor \)。定义： \( parent[ u][ k ] \) 表示节点 \( u \) 向上跳 \( 2^k \) 步后到达的节点。如果跳 \( 2^k \) 步后超过了根节点，则设为 -1 或 0（表示不存在）。特别地，\( parent[ u][ 0 ] \) 就是 \( u \) 的直接父节点（当 \( u \) 不是根时）。这样，我们就可以利用这些预处理信息，在 \( O(\log n) \) 时间内完成任意大步长的向上跳跃。步骤 3：预处理阶段选择根节点：通常选择节点 1 作为根，进行深度优先搜索（DFS）或广度优先搜索（BFS），计算出每个节点的深度 \( depth[ u] \) 和直接父节点 \( parent[ u][ 0 ] \)。伪代码（DFS）：计算倍增表：对于 \( k = 1 \) 到 \( \lfloor \log_ 2 n \rfloor \)：对于每个节点 \( u \)：如果 \( parent[ u][ k-1 ] \) 存在（不为 -1）： \( parent[ u][ k] = parent[ parent[ u][ k-1] ][ k-1 ] \) 否则： \( parent[ u][ k ] = -1 \)（表示不存在）解释：要跳到 \( 2^k \) 步，可以先跳 \( 2^{k-1} \) 步到节点 \( parent[ u][ k-1 ] \)，再从那里跳 \( 2^{k-1} \) 步。这利用了 \( 2^{k-1} + 2^{k-1} = 2^k \)。预处理时间复杂度：每个节点有 \( O(\log n) \) 个状态，总 \( O(n \log n) \)。步骤 4：查询 LCA 的倍增算法给定查询 \( (u, v) \)：调整深度：如果 \( depth[ u] < depth[ v ] \)，交换 \( u \) 和 \( v \)，使得 \( u \) 是较深的节点。然后，将 \( u \) 向上移动，直到与 \( v \) 深度相同。具体操作：设差 \( d = depth[ u] - depth[ v] \)。将 \( d \) 表示为二进制，对于每个二进制位 \( k \)（从高到低），如果 \( d \) 的第 \( k \) 位为 1，就将 \( u \) 跳到 \( parent[ u][ k ] \)。例如，若 \( d = 5 \)（二进制 101），则先跳 \( 2^2 = 4 \) 步，再跳 \( 2^0 = 1 \) 步。如果此时 \( u == v \) ，那么 LCA 就是 \( u \)（因为 \( v \) 是 \( u \) 的祖先）。否则，同时向上跳：从最大的 \( k = \lfloor \log_ 2 n \rfloor \) 开始向下尝试到 0：如果 \( parent[ u][ k] != parent[ v][ k ] \)（即跳 \( 2^k \) 步后，两者仍不同）：将 \( u \) 跳到 \( parent[ u][ k] \)，将 \( v \) 跳到 \( parent[ v][ k ] \)。这个循环结束时，\( u \) 和 \( v \) 会处于 LCA 的直接子节点位置（即它们再向上一步就是 LCA）。返回 LCA ：最后，\( parent[ u][ 0] \)（或 \( parent[ v][ 0 ] \)）就是 LCA。查询时间复杂度：每次调整深度和同时向上跳都是 \( O(\log n) \)。步骤 5：举例说明假设树如下（以 1 为根）：深度：depth[ 1]=0, depth[ 2]=1, depth[ 3]=1, depth[ 4]=2, depth[ 5]=2, depth[ 6 ]=2。预处理 parent 表（只列部分）： parent[ 2][ 0]=1, parent[ 2][ 1 ]=-1（因为跳 2^1=2 步超根） parent[ 4][ 0]=2, parent[ 4][ 1]=1（因为 parent[ 4][ 1] = parent[ parent[ 4][ 0] ][ 0] = parent[ 2][ 0 ] = 1）查询 LCA(4, 5)： depth[ 4]=2, depth[ 5 ]=2，深度相同。同时向上跳：最大 k=1（因为 n=6，log2(6)≈2，但实际只用到1）。 k=1：parent[ 4][ 1]=1, parent[ 5][ 1]=? 先算 parent[ 5][ 0]=2, parent[ 5][ 1]=parent[ 2][ 0 ]=1。两者相等，所以不跳（因为我们要找最后一次跳后仍不同的情况）。 k=0：parent[ 4][ 0]=2, parent[ 5][ 0 ]=2，相等，不跳。循环结束，此时 u=4, v=5。返回 parent[ u][ 0 ] = 2，即 LCA 是 2。查询 LCA(4, 6)： depth[ 4]=2, depth[ 6 ]=2，深度相同。同时向上跳： k=1：parent[ 4][ 1]=1, parent[ 6][ 1]=? parent[ 6][ 0]=3, parent[ 6][ 1]=parent[ 3][ 0 ]=1。相等，不跳。 k=0：parent[ 4][ 0]=2, parent[ 6][ 0 ]=3，不相等。所以 u 跳到 2，v 跳到 3。现在 u=2, v=3。继续 k=0：parent[ 2][ 0]=1, parent[ 3][ 0 ]=1，相等，不跳。返回 parent[ u][ 0 ] = 1，LCA 是 1。步骤 6：算法总结预处理：DFS 计算 depth 和 parent[ u][ 0]，然后动态规划填充 parent[ u][ k ] 表。查询：通过二进制拆分快速调整深度，然后从大到小尝试跳跃，找到 LCA。时间复杂度：预处理 \( O(n \log n) \)，查询 \( O(\log n) \)。空间复杂度：\( O(n \log n) \) 存储 parent 表。倍增算法是 LCA 问题的经典在线解法，高效且易于实现，广泛用于树上的路径查询问题。