practice/lca_binarylifting.cpp at master · Autoratch/practice · GitHub

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 = 1e5 + 1;

int n,q;
int dp[21][N],lv[N];
vector<int> adj[N];

void dfs(int u,int p,int l)
{
    dp[0][u] = p,lv[u] = l;
    for(int v : adj[u]) dfs(v,u,l+1);
}

int lca(int a,int b)
{
    if(lv[a]<lv[b]) swap(a,b);
    for(int i = 20;i >= 0;i--) if(lv[dp[i][a]]>=lv[b]) a = dp[i][a];
    if(a==b) return a;
    for(int i = 20;i >= 0;i--) if(dp[i][a]!=dp[i][b]) a = dp[i][a],b = dp[i][b];
    return dp[0][a];
}

int main()
{
    ios_base::sync_with_stdio(0); cin.tie(0);

    cin >> n;

    for(int i = 0;i < n-1;i++)
    {
        int a,b;
        cin >> a >> b;
        adj[a].push_back(b);
    }

    dfs(0,0,1);

    for(int i = 1;i <= 20;i++) for(int j = 1;j <= n;j++) dp[i][j] = dp[i-1][dp[i-1][j]];

    cin >> q;

    while(q--)
    {
        int a,b;
        cin >> a >> b;
        cout << lca(a,b) << '\n';
    }
}