xxx 最小公共祖先（LCA）问题的欧拉序列与RMQ解法 题目描述 给定一棵有根树和若干查询，每个查询要求两个节点的最小公共祖先（LCA），即深度最深的公共祖先。需要高效处理多个查询。 解题过程 问题分析 朴素解法对每个查询向上回溯会超时（O(n) 每查询）。 目标：利用预处理将每次查询优化到 O(1) 时间复杂度。 核心思路 步骤1：DFS生成欧拉序列 从根节点深度优先搜索（DFS），记录每次访问节点时的 顶点 和 深度 ： 欧拉序列 Euler[1..2n-1] ：按DFS访问顺序记录节点。 深度序列 Depth[1..2n-1] ：记录对应节点的深度。 首次出现位置 First[u] ：节点u在欧拉序列中第一次出现的下标。 示例：对树 1-2, 1-3 ，DFS从1开始： 欧拉序列： [1,2,1,3,1] 深度序列： [0,1,0,1,0] First[ 1]=1, First[ 2]=2, First[ 3 ]=4。 步骤2：LCA转换为RMQ问题 查询LCA(u,v)等价于在深度序列中求区间 [First[u], First[v]] （假设First[ u] ≤ First[ v ]）的最小值对应的节点。 原因：欧拉序列中u到v的路径覆盖了它们的LCA，且LCA是路径中深度最小的节点。 步骤3：RMQ的O(1)查询 使用 稀疏表（Sparse Table） 预处理深度序列： 构建二维数组 ST[k][i] ，存储区间 [i, i+2^k-1] 的最小深度值的下标。 预处理时间复杂度：O(n log n)。 查询区间 [l, r] 时，取长度 k = log2(r-l+1) ，比较 ST[k][l] 和 ST[k][r-2^k+1] 的最小值。 算法步骤 预处理阶段 ： DFS生成欧拉序列和深度序列，记录First数组。 构建稀疏表ST用于深度序列的RMQ。 查询阶段 ： 输入节点u、v，设 l=First[u] , r=First[v] （若l>r则交换）。 查询深度序列中区间[ l, r ]的最小深度对应的下标pos。 输出欧拉序列中该位置的节点 Euler[pos] 即为LCA。 实例演示 树：边集 (1,2), (1,3), (2,4), (2,5)，根节点为1。 DFS访问顺序：1→2→4→2→5→2→1→3→1。 欧拉序列： [1,2,4,2,5,2,1,3,1] 深度序列： [0,1,2,1,2,1,0,1,0] First数组：First[ 1]=1, First[ 2]=2, First[ 4]=3, First[ 5]=5, First[ 3 ]=8。 查询LCA(4,5)： l=First[ 4]=3, r=First[ 5 ]=5。 深度序列区间[ 3,5]为 [2,1,2] ，最小深度1对应下标4。 Euler[ 4 ]=2，故LCA(4,5)=2。 复杂度分析 预处理：DFS O(n)，稀疏表构建 O(n log n)。 查询：每次 O(1)。 适合多次查询的场景（如q次查询总复杂度O(n log n + q)）。