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

题目描述
给定一棵有根树和若干查询，每个查询要求两个节点的最近公共祖先（LCA）。要求高效处理多组查询。

解题过程

1. 问题分析

   • LCA 是树中两个节点的公共祖先中深度最大的节点。
   • 直接暴力求解（如交替向上跳转）的时间复杂度为 O(h)（h 为树高），在多次查询时效率低。
   • 目标：通过预处理，将每次查询的复杂度降至 O(log h)。

2. 算法核心思想

   • 倍增法：预处理每个节点向上跳 2^k 步的祖先，利用二进制拆分思想快速跳转。
   • 步骤：
     a. 预处理每个节点的深度和祖先表（parent[k][u] 表示 u 的 2^k 级祖先）。
     b. 查询时先将两个节点调整到同一深度，再同时向上跳转至 LCA 的下一层。

3. 详细步骤
   步骤 1：预处理深度和直接父节点

   • 通过 DFS 或 BFS 遍历树，记录每个节点的深度 depth[u] 和直接父节点 parent[0][u]（即 2^0 级祖先）。

   步骤 2：构建倍增表

   • 设 k_max 为满足 2^{k_max} ≤ 树的最大深度 的最大整数。
   • 递推计算祖先表：

     for k = 1 to k_max:
         for each node u:
             parent[k][u] = parent[k-1][ parent[k-1][u] ]  // 跳 2^k 步 = 先跳 2^{k-1} 步，再跳 2^{k-1} 步
     

   • 若跳转后超出根节点，则记为 -1 或 0（依节点编号而定）。

   步骤 3：查询 LCA(u, v)
   a. 调整深度：

   • 若 depth[u] < depth[v]，交换 u 和 v 保证 u 更深。
   • 将 u 向上跳至与 v 同一深度：

     for k = k_max down to 0:
         if depth[u] - 2^k >= depth[v]:
             u = parent[k][u]
     

   b. 若此时 u == v，直接返回 u（v 是 u 的祖先）。
   c. 同步上跳：

   for k = k_max down to 0:
       if parent[k][u] != parent[k][v]:  // 避免跳过 LCA
           u = parent[k][u]
           v = parent[k][v]
   

   • 循环结束后，u 和 v 位于 LCA 的下一层，故 LCA = parent[0][u]。

4. 复杂度分析

   • 预处理：O(n log n)（存储祖先表）。
   • 单次查询：O(log n)。
   • 适合处理海量查询的场景。

5. 关键点

   • 跳转时从大到小尝试 2^k 步，确保不跳过目标。
   • 同步上跳时通过比较祖先是否相同来保守跳转，最终定位到 LCA 的下一层。