倍增法

Code:

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
#include<bits/stdc++.h>
#define endl '\n' 
using i64 = long long;
using namespace std;
signed main(){
    std::ios::sync_with_stdio(false);cin.tie(0);
    int n, m, s; cin >> n >> m >> s;
    vector<vector<int>> e(n + 1);
    vector<vector<int>> fa(n + 1, vector<int>(30));
    //fa[u][i]表示以u为根结点，往上2^i层次的父亲编号
    vector<int>dep(n + 1);
    for (int i = 1; i < n;i++){
        int u, v;
        cin >> u >> v;
        e[u].emplace_back(v);
        e[v].emplace_back(u);
    }
    auto dfs = [&](auto dfs, int u, int f, int depth) -> void
    {
        if(u!=s){
            fa[u][0] = f;
            for (int i = 1; (1 << i) <= depth;i++) //预处理各父亲结点的编号
                fa[u][i] = fa[fa[u][i - 1]][i - 1];
        }
        dep[u] = depth;
        for(auto it:e[u])
            if(it!=f)
                dfs(dfs, it, u, depth + 1);
    };
    auto lca = [&](int x, int y) -> int {
        if(dep[x]!=dep[y]){ //使x与y跳到同一高度
            if (dep[x] < dep[y]) swap(x, y); 
            int dis = dep[x] - dep[y];
            int cur = x;
            for (int i = 20; i >= 0; i--)
                if (dis >= (1 << i))
                    cur = fa[cur][i], dis -= 1 << i;
            x = cur;
        }
        if(x==y)
            return x;
        for (int i = 20; i >= 0;i--)
            if (dep[x] >= (1 << i) && fa[x][i] != fa[y][i])
                x = fa[x][i], y = fa[y][i];
        return fa[x][0];
    };
    dfs(dfs, s, -1, 0);
    while(m--){
        int u, v;
        cin >> u >> v;
        cout << lca(u, v) << endl;
    }
    return 0;
}