Talk is Cheap, Show Me the Code!

0%

树链剖分

Posted on In

两次dfs， 第一次求出son[x], 即重儿子的编号； 第二次求出top[x], 即x所在重链的根
结论， 每个点最多跳logn条重链，就可以到达树的根

用树链剖分可以求LCA

输入描述:

n代表点的个数
n-1条边

输出描述:

i, son[i], top[i]

示例1
输入

14 1
1 2
1 3
1 4
2 5
2 6
6 11
6 12
3 7
4 8
4 9
4 10
9 13
13 14
8 14 // m

输出

1 4 1
2 6 2
3 7 3
4 9 1
5 0 5
6 11 2
7 0 3
8 0 8
9 13 1
10 0 10
11 0 2
12 0 12
13 14 1
14 0 1
4

alt exg
shulian.cppview raw
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
65
#include <iostream>
#include <cstring>
#include <vector>
using namespace std;

const int N = 100010;
vector<int>edges[N];

int fa[N], dep[N], son[N], top[N], sz[N];
int n, m;

// get son vector
void dfs(int x, int f, int d){
    fa[x] = f, dep[x] = d, sz[x] = 1, son[x] = 0;
    for(int i=0;i<edges[x].size();i++){
        int y = edges[x][i];
        if(y==f) continue;
        dfs(y, x, d+1);
        sz[x] += sz[y];
        if(sz[son[x]] < sz[y]) son[x] = y;
    }
}

// get top vector
void dfs2(int x, int f, int tp){
    top[x] = tp; ID[x] = ++tot;
    if(son[x]) dfs2(son[x], x, tp);
    for(int i=0;i<edges[x].size();i++){
        int y = edges[x][i];
        if(y==f || y == son[x]) continue;
        dfs2(y, x, y);
    }
}

// a和b走向一条重链
int LCA(int a, int b){
    while(top[a]!=top[b]){
        if(dep[top[a]] > dep[top[b]]){
            // ID[top[a]], ID[a] 是一段连续的区间
            a = fa[top[a]];
        }else b = fa[top[b]];
    }
    return dep[a] > dep[b] ? b: a;
}

int main(){
    cin>>n>>m;
    int a, b;
    for(int i=1;i<n;i++){
        scanf("%d%d", &a, &b);
        edges[a].push_back(b);
        edges[b].push_back(a);
    }
    dfs(1, 0, 1);
    dfs2(1,0,1);
    for(int i=1;i<=n;i++){
        printf("%d %d %d\n", i, son[i], top[i]);
    }
// 8 jumps to 8, fa[8] = 4Œ
    for(int i=1;i<=m;i++){
        scanf("%d%d", &a, &b);
        printf("%d\n", LCA(a, b));
    }
    return 0;
}