P3379 【模板】最近公共祖先（LCA）

题目描述

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

输入格式

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

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

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

输出格式

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

输入输出样例 #1

输入 #1

1
2
3
4
5
6
7
8
9
10
5 5 4
3 1
2 4
5 1
1 4
2 4
3 2
3 5
1 2
4 5

输出 #1

1
2
3
4
5
4
4
1
4
4

说明/提示

对于 $30%$ 的数据，$N\leq 10$，$M\leq 10$。

对于 $70%$ 的数据，$N\leq 10000$，$M\leq 10000$。

对于 $100%$ 的数据，$1 \leq N,M\leq 500000$，$1 \leq x, y,a ,b \leq N$，不保证 $a \neq b$。

样例说明：

该树结构如下：

第一次询问：$2, 4$ 的最近公共祖先，故为 $4$。

第二次询问：$3, 2$ 的最近公共祖先，故为 $4$。

第三次询问：$3, 5$ 的最近公共祖先，故为 $1$。

第四次询问：$1, 2$ 的最近公共祖先，故为 $4$。

第五次询问：$4, 5$ 的最近公共祖先，故为 $4$。

故输出依次为 $4, 4, 1, 4, 4$。

代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
#include <bits/stdc++.h>
using namespace std;
const int N = 4e6 + 10;
vector<int> G[N];
vector<pair<int, int>> Q[N];
int fa[N], vis[N];
int ans[N];
int n, m, p;
inline void addegde (int u, int v) {
    G[u].push_back(v);
    G[v].push_back(u);
}
inline void addquery(int u, int v, int ID) {
    Q[u].push_back({v, ID});
    Q[v].push_back({u, ID});
}
inline int find(int x) {
    return fa[x] == x ? x : fa[x] = find(fa[x]);
} 
void dfs(int u) {
    fa[u] = u;
    vis[u] = 1;
    for(int v : G[u]) {
        if (vis[v]) continue;
        dfs(v);
        fa[v] = u;
    }
    for(pair<int, int> pp : Q[u]) {
        int v = pp.first;
        if(!vis[v]) continue;
        ans[pp.second] = find(v);
    }
}
int main() {
    scanf("%d%d%d", &n, &m, &p);
    int x, y;
    for(int i=1; i<n; i++) {
        scanf("%d%d", &x, &y);
        addegde(x, y);
    }
    for(int i=1; i<=m; i++) {
        scanf("%d%d", &x, &y);
        addquery(x, y, i);
    }
    dfs(p);
    for(int i=1; i<=m; i++) {
        printf("%d\n", ans[i]);
    }
    return 0;
}

复杂度 O(n+m)