xxx 最小公共祖先（LCA）问题的欧拉序列与RMQ解法 题目描述 给定一棵有根树和若干查询，每个查询要求两个结点的最近公共祖先（LCA）。要求通过预处理，使得每次查询能在常数时间内完成。已知树的结点数为 \(n\)，查询数为 \(q\)，需设计高效算法。 解题过程 1. 问题分析 LCA 问题常见应用包括树结构中的路径查询、网络路由等。 暴力法（直接向上跳转）每次查询耗时 \(O(h)\)（\(h\) 为树高），最坏情况（链状树）为 \(O(n)\)，总体 \(O(nq)\)，效率低。 目标：利用欧拉序列将 LCA 问题转化为 RMQ 问题，再通过 RMQ 的稀疏表（Sparse Table）实现 \(O(1)\) 查询。 2. 核心思路 欧拉序列（Euler Tour） ：对树进行 DFS，记录每次访问的结点（包括回溯时）。序列长度为 \(2n-1\)。 深度序列 ：记录欧拉序列中每个结点的深度。 首次出现位置 ：记录每个结点在欧拉序列中第一次出现的下标。 关键性质 ：结点 \(u\) 和 \(v\) 的 LCA 是欧拉序列中 \(u\) 的首次位置到 \(v\) 的首次位置区间内深度最小的结点。 3. 算法步骤 步骤 1：生成欧拉序列与深度序列 初始化空列表 euler 和 depth 。 从根节点开始 DFS： 进入结点 u 时，将 u 加入 euler ，其深度加入 depth 。 递归访问每个未访问的子结点。 回溯到 u 时，再次将 u 加入 euler ，其深度加入 depth （注意：回溯时深度与进入时相同）。 示例（树：1-2, 1-3, 3-4）： Euler: [ 1,2,1,3,4,3,1 ] Depth: [ 0,1,0,1,2,1,0 ] 步骤 2：记录首次出现位置 遍历 euler ，记录每个结点第一次出现的下标到数组 first_occurrence 。 示例： first_occurrence[1]=0 , first_occurrence[2]=1 , first_occurrence[3]=3 , first_occurrence[4]=4 。 步骤 3：转化为 RMQ 问题 查询 LCA(u,v) 时，取 l = first_occurrence[u] , r = first_occurrence[v] （若 l>r 则交换）。 在 depth[l..r] 区间中找到最小值的下标 idx ，则 euler[idx] 即为 LCA。 示例：查询 LCA(2,4) → l=1, r=4 → depth[ 1..4]=[ 1,0,1,2] → 最小值0对应下标2 → euler[ 2 ]=1。 步骤 4：RMQ 的稀疏表预处理 构建二维数组 st ， st[j][i] 表示从 i 开始长度为 \(2^j\) 的区间的最小深度值的下标。 递推关系： 基础： st[0][i] = i （长度为1的区间最小值为自身）。 转移：比较 st[j-1][i] 和 st[j-1][i + 2^(j-1)] 的深度，取更小者。 预处理耗时 \(O(n \log n)\)。 步骤 5：RMQ 查询 查询区间 [ l, r ]： 计算 \(k = \lfloor \log_ 2(r-l+1) \rfloor\)。 比较 st[k][l] 和 st[k][r - 2^k + 1] 的深度，返回下标。 每次查询 \(O(1)\)。 4. 复杂度分析 预处理：DFS \(O(n)\) + 稀疏表 \(O(n \log n)\)。 查询：每次 \(O(1)\)。 总复杂度：\(O(n \log n + q)\)。 5. 关键点总结 利用欧拉序列将树结构线性化。 LCA 问题等价于区间最值查询（RMQ）。 稀疏表通过倍增思想实现高效查询。 注意首次出现位置的定义和区间边界的处理。