六、完善程序2

 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

#include <iostream>
#include <vector>
using namespace std;
const int MAXN = 500010;
vector<int> edge[MAXN];
int depth[MAXN], lg[MAXN];
int pa[MAXN][22];
int n, m, r, x, y;

void dfs(int fa, int sn, int dep) {
    depth[sn] = dep;
    pa[sn][0] = fa;
    for(int i = 1; ① ; i++) {
        pa[sn][i] = pa[pa[sn][i - 1]][i - 1];
    }
    for(int i = 0; i < edge[sn].size(); i++) {
        int fn = edge[sn][i];
        if (fn == fa) {
        continue;
        }
    dfs( ② );
    }
}

int solve(int x, int y) {
    if (depth[x] < depth[y]) {
        swap(x, y);
    }
    while(depth[x] > depth[y]) {
    x = ③ ;
    } 
    if(x == y) {
        return x;
    }
    for(int k = lg[depth[x]] - 1; k >= 0; --k) {
        if( ④ ) {
        x = pa[x][k], y = pa[y][k];
        }
    } 
return pa[x][0];
}
int main() {
    cin >> n >> m >> r;
    for(int i = 1; i <= n; i++)
        lg[i] = lg[i - 1] + (1 << lg[i - 1] == i);
    for (int i = 0; i < n - 1; i++) {
        cin >> x >> y;
        edge[x].push_back(y);
        edge[y].push_back(x);
}
    dfs( ⑤ );
    while (m--) {
        cin >> x >> y;
        cout << solve(x, y) << endl;
    }
return 0;
}