xxx 最小公共祖先（LCA）问题的倍增算法 题目描述 给定一棵有根树（包含 n 个顶点，根节点已知）和若干次查询。每次查询给出树中的两个顶点 u 和 v，要求找到它们的最近公共祖先（LCA），即深度最大的、同时是 u 和 v 的祖先的节点。请设计一个高效的算法，预处理这棵树，使得每次查询可以在 O(log n) 时间内完成。 解题过程 问题分析 最近公共祖先（LCA）是树结构中的基本问题，直接遍历的朴素解法（如从 u 和 v 分别向上跳到根节点，记录路径后比较）在单次查询时需要 O(n) 时间，对于多次查询效率低下。 目标是通过预处理，将查询时间优化至 O(log n)。倍增算法利用二进制拆分的思路，通过预计算每个节点的 2^k 级祖先，实现快速跳跃。 预处理：存储父节点信息 首先进行深度优先搜索（DFS）或广度优先搜索（BFS），记录每个节点的深度 depth[ u] 和直接父节点 parent[ u][ 0 ]（即 2^0=1 级祖先）。 定义数组 parent[ u][ k ] 表示节点 u 的 2^k 级祖先。若该祖先不存在，则记为 -1 或 0（依节点编号而定）。 递推关系：parent[ u][ k] = parent[ parent[ u][ k-1] ][ k-1 ]（即 u 的 2^k 级祖先等于 u 的 2^{k-1} 级祖先的 2^{k-1} 级祖先）。 示例 ：若 k=2，则 parent[ u][ 2 ] 是 u 的祖父的祖父（4 级祖先）。 查询过程：分两步调整节点深度 步骤 1：将 u 和 v 调整到同一深度 假设 depth[ u] > depth[ v]，则交换 u 和 v，保证 v 更深。计算深度差 d = depth[ v] - depth[ u ]。将 d 二进制分解，例如 d=5（二进制 101）时，v 先跳 2^2=4 级，再跳 2^0=1 级，到达与 u 同一深度。 跳跃方法 ：从 k = log₂(n) 开始递减到 0，若 depth[ v] - 2^k ≥ depth[ u]，则令 v = parent[ v][ k ]。 步骤 2：同时向上跳跃直到祖先相同 若此时 u = v，说明 LCA 就是 u（或 v）。否则，从 k = log₂(n) 递减到 0： 若 parent[ u][ k] ≠ parent[ v][ k]，说明 u 和 v 的 2^k 级祖先不同，但 LCA 在更上方，此时令 u = parent[ u][ k], v = parent[ v][ k ]。 若 parent[ u][ k] = parent[ v][ k ]，则跳过（避免跳过头）。 最终 u 和 v 的直接父节点 parent[ u][ 0 ] 即为 LCA。 复杂度分析 预处理：DFS/BFS 耗时 O(n)，父数组填充需 O(n log n)（因为 k 最大为 log₂n）。 单次查询：O(log n)。 适合处理多次查询的场景（如 q 次查询，总复杂度 O((n+q) log n)）。 关键点 倍增思想通过二进制拆分将线性跳跃转为对数级。 预处理时需注意节点编号范围和 k 的最大值（通常取 k_ max = ⌊log₂n⌋）。 实际编码时需处理边界情况（如根节点的父节点为 -1）。