最小公共祖先问题的最近公共祖先数据结构（树链剖分法） 题目描述 给定一棵有 \( n \) 个节点的树，以及 \( q \) 次查询，每次查询两个节点 \( u \) 和 \( v \) 的最近公共祖先（LCA）。最近公共祖先定义为同时是 \( u \) 和 \( v \) 的祖先的节点中深度最大的那个节点。要求设计一个高效的在线算法，预处理后能快速回答每次查询。 解题思路 求解 LCA 的经典方法包括 Tarjan 离线算法、倍增法、RMQ 等。树链剖分也是一种高效方法，它将树分解为若干重链，使得树上任意路径可被拆分成 \( O(\log n) \) 条链，从而实现 LCA 查询的 \( O(\log n) \) 时间复杂度。其主要步骤是：通过一次 DFS 标记节点深度、父节点、子树大小和重儿子；再通过一次 DFS 将树按重链划分，标记每个节点所在重链的顶端节点。查询时，通过比较节点所在重链的顶端节点深度，将较深节点向上跳转，直到两节点位于同一条重链，此时较浅节点即为 LCA。 步骤详解 初始化与数据结构定义 树的表示：使用邻接表存储，节点编号为 1 到 \( n \)。 定义数组： parent[] 存储父节点， depth[] 存储深度（根节点深度为 0）， size[] 存储子树节点数， heavy_son[] 存储重儿子（子树最大的儿子）， top[] 存储节点所在重链的顶端节点。 第一次 DFS：标记深度、父节点、子树大小和重儿子 从根节点（如节点 1）开始 DFS，对每个节点： 记录其父节点和深度。 递归处理所有子节点，累加子树大小，并找到子树大小最大的子节点作为重儿子。 递归返回后，节点子树大小包括自身。 第二次 DFS：划分重链 再次从根节点 DFS。对当前节点： 如果节点是重儿子，则与其父节点在同一条重链，继承父节点的链顶端。 否则，以其自身为新链的顶端。 优先递归重儿子，确保同一条重链上的节点 DFS 序连续。 LCA 查询 对于查询的节点 \( u \) 和 \( v \)： 当它们所在重链顶端不同时，将顶端深度较深的节点跳到其顶端的父节点（即跳到上一条重链），直到两者顶端相同。 当它们在同一重链时，深度较浅的节点即为 LCA。 复杂度分析 预处理两次 DFS：\( O(n) \)。 每次查询：每次跳转都使得当前节点深度减小，且链数最多 \( O(\log n) \)，故单次查询 \( O(\log n) \)。 示例 考虑一棵树，节点 1 为根，边为 (1,2), (1,3), (2,4), (2,5), (3,6)。 第一次 DFS 后，假设节点 2 是节点 1 的重儿子（子树大小最大）。划分重链：链 1 包含节点 1,2,4（重儿子路径）；链 2 包含节点 5（新链）；链 3 包含节点 3,6。 查询 LCA(4,6)： 节点 4 在链 1（顶端 1），节点 6 在链 3（顶端 3）。顶端不同，节点 6 的顶端深度 1 更深，将其跳到父节点 3（链 3 顶端更新为节点 3）。 节点 4 顶端 1，节点 3 顶端 3，节点 3 深度 1 更深，跳到父节点 1（链 3 顶端更新为 1）。 两节点顶端相同（均为 1），且在同一重链，深度较浅节点 1 为 LCA。 实现提示 递归 DFS 注意栈溢出风险，可改用栈或增加递归限制。 确保根节点固定，且树是无向图存储。 可扩展树链剖分以支持路径查询（如路径和、最大值等）。