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
66
67
68
69
70
| #include <iostream>
#include <cstdio>
#include <cstring>
#include <algorithm>
using namespace std;
typedef long long ll;
const int N = 5000001;
const int M = 5000001;
int n, m, s, ans;
int fir[N], to[M], nxt[M], cnt, w[N];
void addEdge(int x, int y){
to[++cnt] = y;
nxt[cnt] = fir[x];
fir[x] = cnt;
}
int deep[N], p[N][23], d[N][23];
void dfs(int u){
for(int i = 1; i <= 22; i++){
if(deep[u] < (1<<i)) break;
p[u][i] = p[p[u][i-1]][i-1];
}
for(int i = fir[u]; i ; i=nxt[i]){
if(!deep[to[i]]){
deep[to[i]] = deep[u] + 1;
p[to[i]][0] = u;
dfs(to[i]);
}
}
}
int lca(int u, int v){
if(deep[u] < deep[v]) swap(u, v);
int c = deep[u] - deep[v];
for(int i = 0; i <= 22; i++){
if((1<<i) & c){
u = p[u][i];
}
}
if(u == v) return u;
for(int i = 22; i >= 0; i--){
if(p[u][i] != p[v][i]){
u = p[u][i];
v = p[v][i];
}
}
return p[u][0];
}
int main(){
scanf("%d%d%d", &n, &m, &s);
for(int i=1;i<=n-1;i++){
int x, y;
scanf("%d%d", &x, &y);
addEdge(x, y);
addEdge(y, x);
}
p[s][0] = s;
deep[s] = 1;
dfs(s);
for(int i = 1; i <= m; i++){
int a, b;
scanf("%d%d", &a, &b);
printf("%d\n", lca(a, b));
}
return 0;
}
|
