xxx 最小公共祖先（LCA）问题的欧拉序列与RMQ解法 题目描述 给定一棵有根树和若干查询，每个查询要求两个节点的最小公共祖先（LCA），即深度最深的公共祖先节点。例如，在一棵以节点1为根的树中，查询(5,6)的LCA可能是节点2。要求高效处理多个查询。 解题过程 问题分析 直接暴力求LCA的方法（如交替向上跳）在多次查询时效率低（单次O(h)，h为树高）。 目标：通过预处理，将LCA问题转化为可快速查询的区间最值问题（RMQ）。 关键观察：欧拉序列与深度序列 对树进行深度优先遍历（DFS），记录访问节点的顺序（欧拉序列）和每个节点的深度。 特性：任意两节点u、v的LCA，在欧拉序列中位于u和v第一次出现位置之间，且是深度最小的节点。 预处理步骤 生成欧拉序列与深度序列 ： DFS遍历树，每次访问节点（包括回溯时）都记录节点编号到欧拉序列，并同步记录当前深度。 示例：树边(1-2, 1-3, 2-4, 2-5)，欧拉序列可能为[ 1,2,4,2,5,2,1,3,1]，深度序列为[ 0,1,2,1,2,1,0,1,0 ]。 记录首次出现位置 ： 用数组 first_occurrence 记录每个节点在欧拉序列中第一次出现的位置。 构建RMQ结构 ： 对深度序列构建RMQ表（如Sparse Table），支持O(1)查询区间最小深度对应的欧拉序列索引。 查询处理 对于查询(u,v)，找到它们在欧拉序列中首次出现的位置 L=first_occurrence[u] 、 R=first_occurrence[v] （若L>R则交换）。 在深度序列的区间[ L,R]中，查询最小深度值的索引 idx 。 欧拉序列中 idx 位置的节点即为LCA。 复杂度分析 预处理：DFS O(n)，Sparse Table构建 O(n log n)。 查询：每次O(1)。 适合多次查询的场景（如q次查询总复杂度O(n log n + q)）。 示例 树：1(0) → 2(1) → 4(2), 5(2); 1 → 3(1) 欧拉序列E: [ 1,2,4,2,5,2,1,3,1 ] 深度序列D: [ 0,1,2,1,2,1,0,1,0 ] 查询LCA(4,5)： L=first_ occurrence[ 4]=2, R=first_ occurrence[ 5 ]=4 在D[ 2:4]中找到最小深度1（索引2或4），对应E[ 2]=2或E[ 4 ]=2 → LCA=2。 通过将LCA转化为RMQ，实现了高效查询。