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

题目描述
给定一棵有根树，以及树上的两个节点 u 和 v，我们希望快速找出它们的最近公共祖先（Lowest Common Ancestor, LCA）。最近公共祖先是指同时是 u 和 v 的祖先的节点中，深度最大的那一个。
例如，在下面的树中（根节点为 1），节点 6 和 8 的 LCA 是 3，节点 7 和 9 的 LCA 是 7 本身。

        1
       / \
      2   4
     / \
    3   5
   / \   \
  6   7   8
         /
        9

输入会包含多组查询 (u, v)，要求对每组查询，快速给出它们的 LCA。
核心挑战：在预处理后，实现每次查询的时间复杂度为 O(log n)，其中 n 是树中节点的数量。

解题过程
我们循序渐进地讲解，每一步都力求清晰、准确。

第一步：理解基本思路
最直观的 LCA 求法是：从 u 和 v 各自向上走到根，记录路径，然后找最后一个相同的节点。但这样每次查询是 O(n) 的，太慢。
倍增算法的核心思想是“二进制跳跃”。我们预先计算出每个节点向上跳 2^k 步能到达的祖先节点，这样在查询时，我们可以让 u 和 v 快速跳到相同深度，然后一起向上“大跳”，跳过那些肯定不是 LCA 的祖先，从而加速。

第二步：定义关键数组
设树有 n 个节点，节点编号 1 到 n，根为 root。我们定义：

• depth[u]：节点 u 的深度（根的深度为 0 或 1，这里通常设为 0 或 1 都可，只要统一。为方便，我设根深度为 1）。
• up[u][k]：节点 u 向上跳 2^k 步后到达的祖先节点。如果跳过了根，就记为 0（假设节点编号从 1 开始，0 表示不存在）。
  这里 k 的最大值是多少？因为树最多有 n 个节点，所以向上最多跳 n-1 步。而 2^k ≤ n-1，所以 k_max = floor(log2(n-1))。实际编程时，我们取一个稍大的常数，比如 20（因为 2^20 ≈ 10^6，足够应付大部分情况）。

第三步：预处理 depth 和 up 数组
我们通过一次深度优先搜索（DFS）或广度优先搜索（BFS）来初始化。
以 DFS 为例（从根开始）：

DFS(u, parent):
    depth[u] = depth[parent] + 1
    up[u][0] = parent  // 向上 2^0 = 1 步就是父节点
    for k = 1 to K:
        up[u][k] = up[ up[u][k-1] ][k-1]  // 2^k = 2^{k-1} + 2^{k-1}
    for each child v of u:
        DFS(v, u)

解释：up[u][k] 表示从 u 向上跳 2^k 步。它可以分解为：先跳 2^{k-1} 步到 up[u][k-1]，再从那里跳 2^{k-1} 步，即 up[ up[u][k-1] ][k-1]。
注意，当 up[u][k-1] 为 0 时，up[u][k] 也为 0（因为已经跳出树了）。
这个预处理时间复杂度是 O(n log n)，因为每个节点计算了 O(log n) 个 up 值。

第四步：查询 LCA(u, v)
查询分三步：

1. 将 u 和 v 调整到同一深度
   假设 depth[u] > depth[v]（否则交换）。我们让 u 向上跳，直到深度和 v 相同。
   怎么跳？利用二进制思想。设深度差为 diff = depth[u] - depth[v]。将 diff 写成二进制形式，比如 diff = 13 = 1101_2，那么 u 需要向上跳 8 + 4 + 1 步。这可以通过从大到小枚举 k 实现：

如果 depth[u] > depth[v]:
    for k from K down to 0:
        如果 depth[ up[u][k] ] >= depth[v]（注意：这里比较 depth 是为了保证不会跳过 v 的深度），
        则 u = up[u][k]

注意：因为 depth 是严格递增的，我们可以用 depth[ up[u][k] ] >= depth[v] 来判断跳完后深度还大于等于 v 的深度，这样最终能调到 depth[u] == depth[v]。
这里循环从 K 到 0 是为了能跳大的步数先跳，快速缩小深度差。

2. 特判：如果此时 u == v，那么 LCA 就是 u（或 v），直接返回。

3. u 和 v 一起向上跳
   此时 u 和 v 在同一深度，但可能还不是同一个节点。我们尝试让它们一起向上跳，但不能跳过 LCA。
   策略是：从最大的步长 k 开始尝试，如果 up[u][k] != up[v][k]，说明这个跳跃不会使它们相遇（即不会跳到 LCA 或更高），就跳上去。最后，u 和 v 会停在 LCA 的直接子节点上。

for k from K down to 0:
    if up[u][k] != up[v][k]:
        u = up[u][k]
        v = up[v][k]

循环结束后，u 和 v 的父节点就是 LCA。所以 LCA 是 up[u][0]（也等于 up[v][0]）。

第五步：完整算法示例
以前面的树为例，假设查询 LCA(6, 9)：

• 预处理 depth 和 up 数组（略）。
• 查询：
  1. depth[6]=4, depth[9]=5，所以让 9 向上跳 diff=1 步到 8（此时 depth[8]=4）。
  2. 现在 u=6, v=8，深度相同但不同节点。
  3. 一起向上跳：最大 k=2（因为 n=9, 2^2=4 足够）。
     k=2: up[6][2]=1, up[8][2]=1，相等，不跳。
     k=1: up[6][1]=3, up[8][1]=2，不等，所以 u=3, v=2。
     k=0: up[3][0]=2, up[2][0]=1，不等，所以 u=2, v=1。
  4. 结束，LCA = up[u][0] = up[2][0] = 1。正确。

第六步：复杂度分析

• 预处理：O(n log n)，需要 DFS/BFS 一次，每个节点计算 O(log n) 个祖先。
• 每次查询：O(log n)，因为循环最多 O(log n) 次。
• 空间：O(n log n) 存储 up 数组。

第七步：边界情况

• 树为一条链：依然正确，每次跳的步长会指数级减少。
• u 或 v 是根：在第一步调整深度时，可能会让深的节点跳到根，然后特判 u==v 成立。
• 查询的两个节点相同：在第一步调整深度时，深度相同，然后特判 u==v 直接返回。

第八步：实现提示

• 通常用邻接表存树。
• 预处理时，根节点的父节点设为 0，up[root][0]=0。
• 在比较深度时，如果 depth 从 1 开始，那么当 up[u][k] 为 0 时 depth[0] 应设为 0，以保证比较正确。

总结
倍增算法是求解 LCA 问题的经典在线算法，思路清晰，实现简单，且时间和空间复杂度较为平衡。它利用了二进制表示任意数的特性，将向上跳的步数分解为 2 的幂次之和，从而实现了快速跳跃。