最小公共祖先（LCA）问题的离线Tarjan算法
字数 4500 2025-12-20 08:03:17

最小公共祖先（LCA）问题的离线Tarjan算法

题目描述

给定一棵包含 \(n\) 个节点的树（树是无向无环连通图）和 \(m\) 个询问，每个询问指定树中的两个节点 \(u\) 和 \(v\)。你的任务是回答每个询问，输出节点 \(u\) 和 \(v\) 的最小公共祖先（Lowest Common Ancestor, LCA），即同时是 \(u\) 和 \(v\) 祖先的那些节点中深度最深的那个节点。

例如，给定一棵树：

        1
       / \
      2   3
     / \   \
    4   5   6
  • 对于询问 (4, 5)，LCA 是节点 2。
  • 对于询问 (4, 6)，LCA 是节点 1。

我们需要一个算法，能高效地处理所有 \(m\) 个询问。离线Tarjan算法是一种利用深度优先搜索（DFS）和并查集（Union-Find Set）的离线算法，可以在 \(O(n + m \alpha(n))\) 的时间复杂度内解决这个问题，其中 \(\alpha(n)\) 是反阿克曼函数，通常可以看作常数。

解题过程

为了循序渐进地理解，我们分步讲解算法的核心思想、数据结构、操作流程和一个完整例子。

第一步：理解核心思想

这个算法的核心是深度优先搜索（DFS）遍历树，并巧妙地利用并查集来合并节点集合，从而在遍历过程中回答与当前节点相关的查询。

基本流程：

  1. 从树的根节点开始进行深度优先搜索。
  2. 在访问一个节点 \(u\) 时，我们将其视为一棵单独的子树，并将其所在的集合（初始时只包含自己）并入其父节点所在的集合（通过并查集的 union 操作）。
  3. 在访问完一个节点 \(u\) 及其所有子树后，将节点 \(u\) 标记为“已访问完成”（visited）。
  4. 当节点 \(u\) 被标记为“已访问完成”时，我们可以回答所有形如 (u, v) 的查询。如果此时节点 \(v\) 也已经被“访问完成”，那么它们的 LCA 就是 find(v)（即并查集查询操作返回的 \(v\) 所在集合的代表元，这个代表元是在DFS回溯过程中确定的当前子树的“根”）。

原理简述：
当我们处理到节点 \(u\) 的某个查询 (u, v) 时，如果 \(v\) 尚未访问，那么我们稍后会在访问到 \(v\) 时处理这个查询。如果 \(v\) 已经访问完成，这意味着在DFS回溯时，包含 \(v\) 的子树已经“闭合”，它们的集合代表元（通过 find(v) 找到的节点）就是 \(u\) 和 \(v\) 所在分支最早分叉的那个节点，也就是它们的 LCA。

第二步：数据结构准备

我们需要定义和初始化以下几个结构：

  1. 邻接表 tree：

    • 存储树的边。这是一个大小为 \(n+1\) 的列表（假设节点编号从1到 \(n\)）。
    • tree[u] 存储与节点 \(u\) 直接相连的子节点列表。
    • 由于树是无向图，我们需要在构建邻接表时记录父节点，避免在DFS中走回头路。通常，在DFS时通过参数 parent 来避免。

  2. 查询列表 queries：

    • 存储所有需要回答的询问。因为询问 (u, v) 是双向的，我们通常为每个询问存储两次，一次以 \(u\) 为键，一次以 \(v\) 为键。
    • 可以用一个大小为 \(n+1\) 的列表，queries[u] 存储所有与 \(u\) 相关的查询对（邻居节点，查询编号）。

  3. 并查集：

    • 主要包括 parent[] 数组（记录每个节点在并查集中的直接父节点）和可选的 rank[] 数组（用于按秩合并优化）。
    • 初始化时，parent[u] = u，即每个节点是一个独立的集合。

  4. 访问状态数组 visited：

    • 布尔数组，大小为 \(n+1\)，初始化为 false。当节点被“访问完成”（即其所有子树都已处理完毕）时，标记为 true。

  5. 答案数组 ans：

    • 大小为 \(m\) 的数组，用于存储每个询问的答案。

第三步：算法详细步骤

算法的主体是一个递归的深度优先搜索函数 tarjan_lca(u)：

  1. 初始化：为当前节点 \(u\) 创建独立的并查集集合（通常初始化时已做好）。
  2. 遍历子节点：
    • 对 \(u\) 的每一个子节点 \(v\)（排除其父节点）：
    • 递归调用 tarjan_lca(v) 处理以 \(v\) 为根的子树。
    • 递归返回后，执行并查集合并操作：union(u, v)。此时，v 所在集合的代表元将被设置为 \(u\)（或者 \(u\) 所在集合的代表元）。
  3. 标记访问完成：处理完所有子节点后，将 visited[u] 设为 true。
  4. 处理与 \(u\) 相关的所有查询：
    • 遍历 queries[u] 列表中的每一个查询 (v, query_id)。
    • 如果 visited[v] 为 true，则说明节点 \(v\) 已经被完全访问。此时，节点 \(u\) 和 \(v\) 的 LCA 就是 find(v)（在并查集中查找 \(v\) 所在集合的代表元）。将 ans[query_id] 赋值为 find(v)。
    • 如果 visited[v] 为 false，则暂时不处理，等待从 \(v\) 那边访问时再处理。

注意：由于每个询问 (u, v) 被存储了两次（在 queries[u] 和 queries[v] 中各一次），所以当 visited[v] 为 true 时，我们只会在处理 u 的查询时计算一次答案，而处理 v 的查询时由于 visited[u] 也为 true，会计算第二次。但我们可以通过查询编号 query_id 确保答案只被正确设置一次（第二次时，ans[query_id] 可能已被赋值，可以直接跳过，或者覆盖为相同值也没问题）。

第四步：一个完整的例子

考虑下面的树（根为1）：

        1
       / \
      2   3
     / \
    4   5

我们有3个询问：

  1. Query 0: (4, 5)
  2. Query 1: (4, 3)
  3. Query 2: (5, 3)

初始化：

  • 邻接表 tree：
    tree[1] = [2, 3]
    tree[2] = [1, 4, 5]
    tree[3] = [1]
    tree[4] = [2]
    tree[5] = [2]
  • 查询列表 queries（每个元素是 (neighbor, query_id)）：
    queries[4] = [(5, 0), (3, 1)]
    queries[5] = [(4, 0), (3, 2)]
    queries[3] = [(4, 1), (5, 2)]
  • 并查集 parent = [1,2,3,4,5]（索引0不用）。
  • visited = [False, False, False, False, False]
  • ans = [-1, -1, -1]

执行 tarjan_lca(1)：

  1. 节点1：子节点是2和3。先处理子节点2。
  2. 递归调用 tarjan_lca(2)：
    • 子节点是4和5（排除父节点1）。先处理子节点4。
    • 递归调用 tarjan_lca(4)：
      • 节点4是叶子节点，没有子节点（除了父节点2）。
      • 标记 visited[4] = True。
      • 处理 queries[4]：
        • (5, 0): visited[5] 是 False，暂不回答。
        • (3, 1): visited[3] 是 False，暂不回答。
      • 返回。
    • 处理完节点4后，合并：union(2, 4)。假设合并后，find(4) 返回2。
    • 接着处理子节点5。
    • 递归调用 tarjan_lca(5)：
      • 节点5是叶子节点。
      • 标记 visited[5] = True。
      • 处理 queries[5]：
        • (4, 0): visited[4] 是 True！find(4) 返回2。所以 ans[0] = 2。
        • (3, 2): visited[3] 是 False，暂不回答。
      • 返回。
    • 处理完节点5后，合并：union(2, 5)。假设合并后，find(5) 返回2。
    • 标记 visited[2] = True。
    • 处理 queries[2]（例子中未存储关于2的查询，所以无事可做）。
    • 返回节点1。
  3. 处理完节点2后，合并：union(1, 2)。现在，find(2)、find(4)、find(5) 都返回1。
  4. 接着处理节点1的子节点3。
  5. 递归调用 tarjan_lca(3)：
    • 节点3是叶子节点（除了父节点1）。
    • 标记 visited[3] = True。
    • 处理 queries[3]：
      • (4, 1): visited[4] 是 True，find(4) 返回1。所以 ans[1] = 1。
      • (5, 2): visited[5] 是 True，find(5) 返回1。所以 ans[2] = 1。
    • 返回。
  6. 处理完节点3后，合并：union(1, 3)。
  7. 最后，标记 visited[1] = True，处理 queries[1]（本例中没有），算法结束。

最终答案：
ans = [2, 1, 1]，对应：

  • (4,5) 的 LCA 是 2。
  • (4,3) 的 LCA 是 1。
  • (5,3) 的 LCA 是 1。

第五步：算法总结与复杂度

  1. 时间复杂度：
    • DFS遍历树：\(O(n)\)。
    • 对每个节点，处理与之相关的所有查询。每个查询被处理两次（从两端各一次），但每次处理是 \(O(1)\) 加上并查集操作。
    • 并查集的 find 和 union 操作，在路径压缩和按秩合并优化下，单次操作平均接近 \(O(\alpha(n))\)。
    • 总复杂度：\(O(n + m \alpha(n))\)，在实践上可以视为 \(O(n + m)\)。
  2. 空间复杂度：
    • 存储树：\(O(n)\)。
    • 存储查询：\(O(m)\)。
    • 并查集和访问数组：\(O(n)\)。
    • 总空间：\(O(n + m)\)。

优点：

  • 时间复杂度优秀，适合处理大规模树和大量查询。
  • 离线算法，一次性处理所有查询，适合静态树结构。

缺点：

  • 是离线算法，必须预先知道所有查询，无法在线即时回答新出现的查询。
  • 需要递归（或栈模拟递归）进行DFS，对于深度非常大的树需要注意栈溢出风险。

希望这个对离线Tarjan LCA算法的逐步讲解，能够帮助你透彻理解它的运作机制。它的巧妙之处在于将DFS回溯过程与并查集合并相结合，使得在遍历过程中就能高效地回答关于最近公共祖先的查询。

最小公共祖先（LCA）问题的离线Tarjan算法 题目描述 给定一棵包含 \( n \) 个节点的树（树是无向无环连通图）和 \( m \) 个询问，每个询问指定树中的两个节点 \( u \) 和 \( v \)。你的任务是回答每个询问，输出节点 \( u \) 和 \( v \) 的 最小公共祖先 （Lowest Common Ancestor, LCA），即同时是 \( u \) 和 \( v \) 祖先的那些节点中深度最深的那个节点。 例如，给定一棵树： 对于询问 (4, 5)，LCA 是节点 2。 对于询问 (4, 6)，LCA 是节点 1。 我们需要一个算法，能高效地处理所有 \( m \) 个询问。 离线Tarjan算法 是一种利用深度优先搜索（DFS）和并查集（Union-Find Set）的离线算法，可以在 \( O(n + m \alpha(n)) \) 的时间复杂度内解决这个问题，其中 \( \alpha(n) \) 是反阿克曼函数，通常可以看作常数。 解题过程 为了循序渐进地理解，我们分步讲解算法的核心思想、数据结构、操作流程和一个完整例子。 第一步：理解核心思想 这个算法的核心是 深度优先搜索 （DFS）遍历树，并巧妙地利用 并查集 来合并节点集合，从而在遍历过程中回答与当前节点相关的查询。 基本流程： 从树的根节点开始进行深度优先搜索。 在访问一个节点 \( u \) 时，我们将其视为一棵单独的子树，并将其所在的集合（初始时只包含自己）并入其父节点所在的集合（通过并查集的 union 操作）。 在访问完一个节点 \( u \) 及其所有子树后，将节点 \( u \) 标记为“已访问完成”（ visited ）。 当节点 \( u \) 被标记为“已访问完成”时，我们可以回答所有形如 (u, v) 的查询。如果此时节点 \( v \) 也已经被“访问完成”，那么它们的 LCA 就是 find(v) （即并查集查询操作返回的 \( v \) 所在集合的代表元，这个代表元是在DFS回溯过程中确定的当前子树的“根”）。 原理简述 ： 当我们处理到节点 \( u \) 的某个查询 (u, v) 时，如果 \( v \) 尚未访问，那么我们稍后会在访问到 \( v \) 时处理这个查询。如果 \( v \) 已经访问完成，这意味着在DFS回溯时，包含 \( v \) 的子树已经“闭合”，它们的集合代表元（通过 find(v) 找到的节点）就是 \( u \) 和 \( v \) 所在分支最早分叉的那个节点，也就是它们的 LCA。 第二步：数据结构准备 我们需要定义和初始化以下几个结构： 邻接表 tree ： 存储树的边。这是一个大小为 \( n+1 \) 的列表（假设节点编号从1到 \( n \)）。 tree[u] 存储与节点 \( u \) 直接相连的子节点列表。 由于树是无向图，我们需要在构建邻接表时记录父节点，避免在DFS中走回头路。通常，在DFS时通过参数 parent 来避免。 查询列表 queries ： 存储所有需要回答的询问。因为询问 (u, v) 是双向的，我们通常为每个询问存储两次，一次以 \( u \) 为键，一次以 \( v \) 为键。 可以用一个大小为 \( n+1 \) 的列表， queries[u] 存储所有与 \( u \) 相关的查询对（邻居节点，查询编号）。 并查集 ： 主要包括 parent[] 数组（记录每个节点在并查集中的直接父节点）和可选的 rank[] 数组（用于按秩合并优化）。 初始化时， parent[u] = u ，即每个节点是一个独立的集合。 访问状态数组 visited ： 布尔数组，大小为 \( n+1 \)，初始化为 false 。当节点被“访问完成”（即其所有子树都已处理完毕）时，标记为 true 。 答案数组 ans ： 大小为 \( m \) 的数组，用于存储每个询问的答案。 第三步：算法详细步骤 算法的主体是一个递归的深度优先搜索函数 tarjan_lca(u) ： 初始化 ：为当前节点 \( u \) 创建独立的并查集集合（通常初始化时已做好）。 遍历子节点 ： 对 \( u \) 的每一个子节点 \( v \)（排除其父节点）： 递归调用 tarjan_lca(v) 处理以 \( v \) 为根的子树。 递归返回后，执行并查集合并操作： union(u, v) 。此时， v 所在集合的代表元将被设置为 \( u \)（或者 \( u \) 所在集合的代表元）。 标记访问完成 ：处理完所有子节点后，将 visited[u] 设为 true 。 处理与 \( u \) 相关的所有查询 ： 遍历 queries[u] 列表中的每一个查询 (v, query_id) 。 如果 visited[v] 为 true ，则说明节点 \( v \) 已经被完全访问。此时，节点 \( u \) 和 \( v \) 的 LCA 就是 find(v) （在并查集中查找 \( v \) 所在集合的代表元）。将 ans[query_id] 赋值为 find(v) 。 如果 visited[v] 为 false ，则暂时不处理，等待从 \( v \) 那边访问时再处理。 注意 ：由于每个询问 (u, v) 被存储了两次（在 queries[u] 和 queries[v] 中各一次），所以当 visited[v] 为 true 时，我们只会在处理 u 的查询时计算一次答案，而处理 v 的查询时由于 visited[u] 也为 true ，会计算第二次。但我们可以通过查询编号 query_id 确保答案只被正确设置一次（第二次时， ans[query_id] 可能已被赋值，可以直接跳过，或者覆盖为相同值也没问题）。 第四步：一个完整的例子 考虑下面的树（根为1）： 我们有3个询问： Query 0: (4, 5) Query 1: (4, 3) Query 2: (5, 3) 初始化 ： 邻接表 tree ： tree[1] = [2, 3] tree[2] = [1, 4, 5] tree[3] = [1] tree[4] = [2] tree[5] = [2] 查询列表 queries （每个元素是 (neighbor, query_id) ）： queries[4] = [(5, 0), (3, 1)] queries[5] = [(4, 0), (3, 2)] queries[3] = [(4, 1), (5, 2)] 并查集 parent = [1,2,3,4,5] （索引0不用）。 visited = [False, False, False, False, False] ans = [-1, -1, -1] 执行 tarjan_lca(1) ： 节点1 ：子节点是2和3。先处理子节点2。 递归调用 tarjan_lca(2) ： 子节点是4和5（排除父节点1）。先处理子节点4。 递归调用 tarjan_lca(4) ： 节点4是叶子节点，没有子节点（除了父节点2）。 标记 visited[4] = True 。 处理 queries[4] ： (5, 0): visited[5] 是 False ，暂不回答。 (3, 1): visited[3] 是 False ，暂不回答。 返回。 处理完节点4后 ，合并： union(2, 4) 。假设合并后， find(4) 返回2。 接着处理子节点5。 递归调用 tarjan_lca(5) ： 节点5是叶子节点。 标记 visited[5] = True 。 处理 queries[5] ： (4, 0): visited[4] 是 True ！ find(4) 返回2。所以 ans[0] = 2 。 (3, 2): visited[3] 是 False ，暂不回答。 返回。 处理完节点5后 ，合并： union(2, 5) 。假设合并后， find(5) 返回2。 标记 visited[2] = True 。 处理 queries[2] （例子中未存储关于2的查询，所以无事可做）。 返回节点1。 处理完节点2后 ，合并： union(1, 2) 。现在， find(2) 、 find(4) 、 find(5) 都返回1。 接着处理节点1的子节点3 。 递归调用 tarjan_lca(3) ： 节点3是叶子节点（除了父节点1）。 标记 visited[3] = True 。 处理 queries[3] ： (4, 1): visited[4] 是 True ， find(4) 返回1。所以 ans[1] = 1 。 (5, 2): visited[5] 是 True ， find(5) 返回1。所以 ans[2] = 1 。 返回。 处理完节点3后 ，合并： union(1, 3) 。 最后 ，标记 visited[1] = True ，处理 queries[1] （本例中没有），算法结束。 最终答案 ： ans = [2, 1, 1] ，对应： (4,5) 的 LCA 是 2。 (4,3) 的 LCA 是 1。 (5,3) 的 LCA 是 1。 第五步：算法总结与复杂度 时间复杂度 ： DFS遍历树：\( O(n) \)。 对每个节点，处理与之相关的所有查询。每个查询被处理两次（从两端各一次），但每次处理是 \( O(1) \) 加上并查集操作。 并查集的 find 和 union 操作，在路径压缩和按秩合并优化下，单次操作平均接近 \( O(\alpha(n)) \)。 总复杂度：\( O(n + m \alpha(n)) \)，在实践上可以视为 \( O(n + m) \)。 空间复杂度 ： 存储树：\( O(n) \)。 存储查询：\( O(m) \)。 并查集和访问数组：\( O(n) \)。 总空间：\( O(n + m) \)。 优点 ： 时间复杂度优秀，适合处理大规模树和大量查询。 离线算法，一次性处理所有查询，适合静态树结构。 缺点 ： 是离线算法，必须预先知道所有查询，无法在线即时回答新出现的查询。 需要递归（或栈模拟递归）进行DFS，对于深度非常大的树需要注意栈溢出风险。 希望这个对离线Tarjan LCA算法的逐步讲解，能够帮助你透彻理解它的运作机制。它的巧妙之处在于将DFS回溯过程与并查集合并相结合，使得在遍历过程中就能高效地回答关于最近公共祖先的查询。