题目：P3379 最近公共祖先（LCA）

如题，给定一棵有根多叉树，请求出指定两个点直接最近的公共祖先．

输入格式#

第一行包含三个正整数 $N,M,S$ ，分别表示树的结点个数、询问的个数和树根结点的序号．

接下来 $N-1$ 行每行包含两个正整数 $x, y$ ，表示 $x$ 结点和 $y$ 结点之间有一条直接连接的边（数据保证可以构成树）．

接下来 $M$ 行每行包含两个正整数 $a, b$ ，表示询问 $a$ 结点和 $b$ 结点的最近公共祖先．

输出格式#

输出包含 $M$ 行，每行包含一个正整数，依次为每一个询问的结果．

数据范围#

对于 $100\%$ 的数据， $1 \leq N,M\leq 5\times10^5$ ， $1 \leq x, y,a ,b \leq N$ ，不保证 $a \neq b$ ．

分析#

LCA（Lowest Common Ancestor）即树上两个节点 $u,v$ 路径上离根最近的公共节点．

常用方法有：

倍增法（预处理 $O(n\log n)$ ，单次查询 $O(\log n)$ ）
树链剖分（重链剖分）
Tarjan 离线算法

最常用、易实现的是倍增法．

倍增法需要：

预处理每个节点的 $2^k$ 级祖先（即 $fa[u][k]$ 表示 $u$ 的第 $2^k$ 级祖先）．
查询时先将 $u,v$ 跳到同一深度，然后一起向上跳，距离从 $2^{\log n}$ 到 $2^0$ ，如果跳到相同的节点就调回来，下一次少跳一些，直到找到最近公共祖先．

具体实现步骤：

建树与初始化
- 用邻接表存树．
- 记录每个节点的深度 $deep[u]$ ．
- 记录每个节点的父节点 $fa[u][0]$ ．
预处理倍增表
- 对每个节点 $u$ ， $fa[u][k] = fa[fa[u][k-1]][k-1]$ ．
- 预处理 $k$ 从 $1$ 到 $\log n$ ．
查询 LCA
- 若 $u,v$ 深度不同，先将较深的节点向上跳到同一深度．
- 然后从大到小枚举 $k$ ，若 $fa[u][k] \neq fa[v][k]$ ，则 $u,v$ 同时跳到各自的 $2^k$ 级祖先．
- 最后 $u$ 和 $v$ 的父节点就是 LCA．

复杂度分析#

预处理： $O(n\log n)$
单次查询： $O(\log n)$

标程#

1
#include <bits/stdc++.h>
2

3
using namespace std;
4

5
const int N = 5e5 + 100;
6

7
int n, m, s;
8
vector<int> edge[N];
9
int deep[N];
10
int fa[N][23];
11

12
// 预处理
13
void getInfo(int t) {
14
  // 预处理父节点
15
  deep[t] = deep[fa[t][0]] + 1;
16
  // 预处理祖宗节点
17
  for (int i = 1; i < 23; ++i)
18
    fa[t][i] = fa[fa[t][i - 1]][i - 1];
19

20
  // 递归处理所有的边
21
  for (int i = 0; i < edge[t].size(); ++i) {
22
    int to = edge[t][i];
23
    if (to == fa[t][0]) continue;
24
    fa[to][0] = t;
25
    getInfo(to);
26
  }
27
}
28

29
// 获得t节点向上跳v格跳到的节点编号
30
int jump(int t, int v) {
31
  for (int i = 22; i >= 0; --i) {
32
    if (v >= (1 << i)) {
33
      t = fa[t][i];
34
      v -= (1 << i);
35
    }
36
  }
37
  return t;
38
}
39

40
// 获取节点x和节点y的lca
41
int lca(int x, int y) {
42
  // 统一深度
43
  if (deep[y] > deep[x]) y = jump(y, deep[y] - deep[x]);
44
  else x = jump(x, deep[x] - deep[y]);
45
  // 处理x和y是同一支上的，有血缘关系的情况
46
  if (x == y) return x;
47

48
  // 向上跳
49
  for (int i = 22; i >= 0; --i) {
50
    if (fa[x][i] == fa[y][i]) continue;
51
    x = fa[x][i], y = fa[y][i];
52
  }
53
  return fa[x][0];
54
}
55

56
int main() {
57
  cin >> n >> m >> s;
58
  for (int i = 1; i <= n - 1; ++i) {
59
    int x, y;
60
    cin >> x >> y;
61
    edge[x].push_back(y);
62
    edge[y].push_back(x);
63
  }
64
  getInfo(s);
65
  for (int i = 1; i <= m; ++i) {
66
    int x, y;
67
    cin >> x >> y;
68
    cout << lca(x, y) << endl;
69
  }
70
  return 0;
71
}

音乐

音乐

输入格式#

输出格式#

数据范围#

分析#

复杂度分析#

标程#

文章分享