树上LCA求两点距离|曾子愚 's Blog

关于使用AI:

本篇文章因人类的想法而被ai创作

本篇文章经过人类审核

AI模型：chatgpt-o1-mini

在计算机算法竞赛中，树（Tree）是一种常见的数据结构，经常需要解决与树相关的各种问题。LCA（Lowest Common Ancestor，最低公共祖先） 是树上一个非常重要的概念，广泛应用于求解两点间距离、路径问题等。本文将详细解释如何在树上使用LCA求两点距离，包括原理、实现方法和一个详细的示例。

1. 基本概念

1.1 树（Tree）

树是一种无环、连通的图，由若干节点（顶点）和边组成。树有一个根节点（Root），其他节点通过边与根相连。树的特点是每两个节点之间唯一一条路径。

1.2 最低公共祖先（LCA）

在一棵树中，给定两个节点 u 和 v，它们的最低公共祖先是离这两个节点最近的共享祖先节点。换句话说，LCA 是所有共同祖先中深度最大的那个。

例如，在以下树中：

节点 4 和 5 的 LCA 是节点 2。
节点 4 和 6 的 LCA 是节点 1。

2. 利用 LCA 计算两点距离

在树中，两点 u 和 v 之间的距离是它们之间的边数。使用 LCA，可以高效地计算这一距离。

2.1 原理

假设树上有以下信息：

每个节点的深度（Depth），即从根节点到该节点经过的边数。
每个节点到根节点的路径。

令 LCA(u, v) 表示 u 和 v 的最低公共祖先。则两点 u 和 v 之间的距离 dist(u, v) 可以表示为：

dist(u, v) = depth(u) + depth(v) - 2 * depth(LCA(u, v))

解释：

depth(u) 是从根节点到 u 的距离。
depth(v) 是从根节点到 v 的距离。
depth(LCA(u, v)) 是从根节点到 u 和 v 的最低公共祖先的距离。
两者之和减去两倍的 LCA 的深度，消除了从根节点到 LCA 的重复部分，得到 u 到 v 的路径长度。

2.2 计算 LCA 的方法

在竞赛中，高效计算 LCA 主要有以下几种方法：

二叉跳表（Binary Lifting）：预处理 O(N log N)，查询 O(log N)。
欧拉序列 + 稀疏表（Euler Tour + Sparse Table）：预处理 O(N) 或 O(N log N)，查询 O(1)。
Tarjan 算法：离线求解所有 LCA 问题。

这里，我们重点讲解 二叉跳表 方法，因为它相对简单且高效，适合竞赛中使用。

2.3 二叉跳表方法详解

2.3.1 思想

二叉跳表（Binary Lifting）通过预处理每个节点在 2^k 路径上的祖先，使得在查询 LCA 时，可以将两个节点逐步提升到同一深度，然后一起跳到更高的祖先，直到找到共同的祖先。

2.3.2 实现步骤

预处理：
- 深度计算：使用 DFS 或 BFS 计算每个节点的深度。
- 祖先表构建：构建 ancestor[k][u] 表，表示节点 u 的第 2^k 个祖先。
LCA 查询：
- 如果 u 和 v 深度不同，先将较深的节点提升到与较浅节点相同的深度。
- 从高到低逐步检查每个 k，若 ancestor[k][u] 与 ancestor[k][v] 不同，则将 u 和 v 同时提升到各自的第 2^k 个祖先。
- 最终，当 u 和 v 有相同的直接父节点时，该父节点即为 LCA。

2.3.3 代码实现（C++）

下面是一个使用二叉跳表的 LCA 实现示例：

#include <bits/stdc++.h>
using namespace std;

const int MAXN = 1e5 + 5; // 最大节点数
const int LOG = 20; // 因为 2^20 > 1e6

int n, q;
vector<vector<int>> adj(MAXN);
int depth_node[MAXN];
int ancestor_table[LOG][MAXN];

// DFS 预处理深度和 2^0 祖先（直接父节点）
void dfs(int u, int parent_u) {
    ancestor_table[0][u] = parent_u;
    for(auto &v : adj[u]) {
        if(v != parent_u) {
            depth_node[v] = depth_node[u] + 1;
            dfs(v, u);
        }
    }
}

// 预处理其他层的祖先
void preprocess() {
    for(int k = 1; k < LOG; ++k) {
        for(int u = 1; u <= n; ++u) {
            if(ancestor_table[k-1][u] != -1)
                ancestor_table[k][u] = ancestor_table[k-1][ancestor_table[k-1][u]];
            else
                ancestor_table[k][u] = -1;
        }
    }
}

// LCA 查询
int lca(int u, int v) {
    if(depth_node[u] < depth_node[v])
        swap(u, v);
    
    // 提升 u 到与 v 相同的深度
    for(int k = LOG-1; k >= 0; --k) {
        if(depth_node[u] - (1 << k) >= depth_node[v]) {
            u = ancestor_table[k][u];
        }
    }

    if(u == v)
        return u;
    
    // 同时提升 u 和 v
    for(int k = LOG-1; k >= 0; --k) {
        if(ancestor_table[k][u] != -1 && ancestor_table[k][u] != ancestor_table[k][v]) {
            u = ancestor_table[k][u];
            v = ancestor_table[k][v];
        }
    }

    // 返回公共祖先
    return ancestor_table[0][u];
}

int main(){
    ios::sync_with_stdio(false);
    cin.tie(0);
    
    cin >> n;
    // 读入树的边
    for(int i = 1; i < n; ++i){
        int u, v;
        cin >> u >> v;
        adj[u].emplace_back(v);
        adj[v].emplace_back(u);
    }

    // 初始化
    memset(ancestor_table, -1, sizeof(ancestor_table));
    depth_node[1] = 0; // 假设1为根
    dfs(1, -1);
    preprocess();

    cin >> q;
    while(q--){
        int u, v;
        cin >> u >> v;
        int ancestor = lca(u, v);
        // 计算距离
        int distance = depth_node[u] + depth_node[v] - 2 * depth_node[ancestor];
        cout << distance << "\n";
    }
}

说明：

预处理阶段：
- 使用 DFS 遍历树，计算每个节点的深度 depth_node[u] 和 ancestor_table[0][u]（直接父节点）。
- 构建二叉跳表 ancestor_table[k][u]，其中 k 表示跳跃的 2^k 层祖先。
查询阶段：
- 对于每个查询的两点 u 和 v，首先通过提升深度使得两点位于相同深度。
- 然后通过逐步提升 u 和 v，直到找到最低公共祖先。
- 最后，利用深度信息计算距离。

3. 示例

让我们通过一个详细的示例来说明如何使用 LCA 求两点的距离。

3.1 示例树

考虑以下树结构（节点编号从 1 到 7）：

节点和边：

节点数 n = 7
边：(1-2), (1-3), (1-4), (2-5), (2-6), (4-7)

3.2 查询

假设有以下查询：

查询距离 5 和 6 之间的距离。
查询距离 5 和 3 之间的距离。
查询距离 5 和 7 之间的距离.
查询距离 3 和 7 之间的距离。

3.3 执行过程

3.3.1 预处理

深度计算（假设根节点为 1）：

depth_node[1] = 0
depth_node[2] = 1
depth_node[3] = 1
depth_node[4] = 1
depth_node[5] = 2
depth_node[6] = 2
depth_node[7] = 2

祖先表构建：

ancestor_table[0][u]:
ancestor_table[0][1] = -1
ancestor_table[0][2] = 1
ancestor_table[0][3] = 1
ancestor_table[0][4] = 1
ancestor_table[0][5] = 2
ancestor_table[0][6] = 2
ancestor_table[0][7] = 4

ancestor_table[1][u] = ancestor_table[0][ancestor_table[0][u]]:
ancestor_table[1][1] = -1
ancestor_table[1][2] = ancestor_table[0][1] = -1
ancestor_table[1][3] = ancestor_table[0][1] = -1
ancestor_table[1][4] = ancestor_table[0][1] = -1
ancestor_table[1][5] = ancestor_table[0][2] = 1
ancestor_table[1][6] = ancestor_table[0][2] = 1
ancestor_table[1][7] = ancestor_table[0][4] = 1

ancestor_table[2][u] = ancestor_table[1][ancestor_table[1][u]]:
ancestor_table[2][1] = -1
ancestor_table[2][2] = ancestor_table[1][-1] = -1
ancestor_table[2][3] = ancestor_table[1][-1] = -1
ancestor_table[2][4] = ancestor_table[1][-1] = -1
ancestor_table[2][5] = ancestor_table[1][1] = -1
ancestor_table[2][6] = ancestor_table[1][1] = -1
ancestor_table[2][7] = ancestor_table[1][1] = -1

// 更高层均为 -1

3.3.2 查询处理

查询 1：`5` 和 `6`

找到 LCA：
- depth_node[5] = 2, depth_node[6] = 2。
- 两者已在相同深度。
- 从高到低检查跳表：
  - k=1，ancestor_table[1][5]=1，ancestor_table[1][6]=1，相同，不需要提升。
  - k=0，ancestor_table[0][5]=2，ancestor_table[0][6]=2，相同。
- LCA is 2.

计算距离：

dist(5,6) = depth_node[5] + depth_node[6] - 2 * depth_node[2]
          = 2 + 2 - 2 * 1
          = 4 - 2
          = 2

查询 2：`5` 和 `3`

找到 LCA：
- depth_node[5] = 2, depth_node[3] = 1。
- 提升 5 到深度 1：
  - k=0, ancestor_table[0][5]=2.
- 现在比较 2 和 3：
  - ancestor_table[0][2]=1, ancestor_table[0][3]=1。
- LCA is 1.

计算距离：

dist(5,3) = depth_node[5] + depth_node[3] - 2 * depth_node[1]
          = 2 + 1 - 2 * 0
          = 3

查询 3：`5` 和 `7`

找到 LCA：
- depth_node[5] = 2, depth_node[7] = 2。
- 已在相同深度。
- 从高到低检查跳表：
  - k=1, ancestor_table[1][5]=1, ancestor_table[1][7]=1, 相同，不需要提升。
  - k=0, ancestor_table[0][5]=2, ancestor_table[0][7]=4, 不同。
- 提升到 ancestor_table[0][5]=2 和 ancestor_table[0][7]=4.
- 继续提升：
  - ancestor_table[0][2]=1, ancestor_table[0][4]=1.
- LCA is 1.

计算距离：

dist(5,7) = depth_node[5] + depth_node[7] - 2 * depth_node[1]
          = 2 + 2 - 2 * 0
          = 4

查询 4：`3` 和 `7`

找到 LCA：
- depth_node[3] = 1, depth_node[7] = 2.
- 提升 7 到深度 1：
  - k=0, ancestor_table[0][7]=4.
- 现在比较 3 和 4：
  - ancestor_table[0][3]=1, ancestor_table[0][4]=1.
- LCA is 1.

计算距离：

dist(3,7) = depth_node[3] + depth_node[7] - 2 * depth_node[1]
          = 1 + 2 - 2 * 0
          = 3

3.4 结果

dist(5,6) = 2
dist(5,3) = 3
dist(5,7) = 4
dist(3,7) = 3

4. 复杂度分析

预处理时间：O(N log N)，其中 N 是节点数。
每次 LCA 查询时间：O(log N)。
空间复杂度：O(N log N)，用于存储跳表。

在计算机算法竞赛中，这样的时间和空间复杂度通常是可以接受的，特别是对于树的节点数在 10^5 左右的情况下。

5. 总结

通过预处理树的深度和二叉跳表，我们可以高效地计算任意两点之间的最低公共祖先（LCA），进而快速计算它们之间的距离。理解并掌握这种方法对于解决树相关的竞赛问题非常重要。希望本文的详细解释和示例能够帮助你更好地理解和应用 LCA 来求解树上的两点距离问题。

1. 基本概念

1.1 树（Tree）

1.2 最低公共祖先（LCA）

2. 利用 LCA 计算两点距离

2.1 原理

解释：

2.2 计算 LCA 的方法

2.3 二叉跳表方法详解

2.3.1 思想

2.3.2 实现步骤

2.3.3 代码实现（C++）

说明：

3. 示例

3.1 示例树

3.2 查询

3.3 执行过程

3.3.1 预处理

3.3.2 查询处理

查询 1：5 和 6

查询 2：5 和 3

查询 3：5 和 7

查询 4：3 和 7

3.4 结果

4. 复杂度分析

5. 总结

NOIP2018-S T3 题解

暴龙

Zengtudor

查询 1：`5` 和 `6`

查询 2：`5` 和 `3`

查询 3：`5` 和 `7`

查询 4：`3` 和 `7`