Luogu P3379 【模板】最近公共祖先（LCA），树链剖分求LCA模板

Problem

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

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

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

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

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

输入输出样例
输入 #1复制
5 5 4
3 1
2 4
5 1
1 4
2 4
3 2
3 5
1 2
4 5
输出 #1复制
4
4
1
4
4
说明/提示
对于 30%30% 的数据，N\leq 10N≤10，M\leq 10M≤10。

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

对于 100%100% 的数据，N\leq 500000N≤500000，M\leq 500000M≤500000。

样例说明：

该树结构如下：

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

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

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

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

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

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

2021/10/4 数据更新 @fstqwq：应要求加了两组数据卡掉了暴力跳。

Codes

• 留个备忘

#include
using namespace std;
typedef long long LL;
#define IOS ios::sync_with_stdio(0), cin.tie(0),cout.tie(0)
const int maxn = 5e5+10;

int n, q, rt;
struct tree{
    vector<int>G[maxn];
    int fa[maxn], siz[maxn], son[maxn], top[maxn], dep[maxn];
    void add(int x, int y){ 
        G[x].push_back(y); 
        G[y].push_back(x);
    }
    void dfs(int x, int f){
        siz[x] = 1;
        for(int y : G[x]){
            if(y==f)continue;
            fa[y] = x;
            dep[y] = dep[x]+1;
            dfs(y,x);
            if(siz[y] > siz[son[x]])son[x] = y;//x的重儿子
            siz[x] += siz[y];
        }
    }
    void dfs(int x, int y, int f){       //轻重链剖分
        top[x] = y;                      //所在链链顶
        if(son[x])dfs(son[x], y,x);      //重链往下去不用更新链顶
        for(int y : G[x]){
            if(y==f)continue;
            if(y==son[x])continue;
            dfs(y,y,x);                  //更新y为链顶 
        }
    }
    //LCA复杂度：暴力O(n), 倍增O(logn~nlogn), TarjianO(logn~n), 树剖O(logn)
    int lca(int x, int y){
        while(top[x] != top[y]){    //不在同一条链上 每次链顶深度较大的点往上爬
            if(dep[top[x]] < dep[top[y]])swap(x,y);
            x = fa[top[x]];         //进入新的链
        }
        if(dep[x] < dep[y])return x;//进入同一条链上时, 深度小的点在前面
        return y;
    }
    void do_lca(int rt){
        dfs(rt,-1);
        dfs(rt,-1,-1);
    }
}treea;

int main(){
    IOS;
    cin>>n>>q>>rt;
    for(int i = 2; i <= n; i++){
        int u, v;  cin>>u>>v;
        treea.add(u,v);
    }
    treea.do_lca(rt);
    for(int i = 1; i <= q; i++){
        int u, v;  cin>>u>>v;
        cout<<treea.lca(u,v)<<"\n";
    }
    return 0;
}

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
51
52
53
54
55
56
57
58
59
60
61
62
63
64