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
| #include<cstdio>
#include<cstring>
#include<algorithm>
#include<cmath>
#include<iostream>
using namespace std ;
const int maxn = 1000005 ;
int n , m , s ;
int head[maxn] , to[maxn] , nex[maxn] , cnt = 0 ;
int father[maxn][20] , dep[maxn] ;
void add ( int x , int y ) { nex[++cnt] = head[x] ; head[x] = cnt ; to[cnt] = y ; }
void dfs ( int x , int fa , int depth ) {
father[x][0] = fa ; dep[x] = depth ;
for ( int i = 1 ; i <= 19 ; i ++ ) {
father[x][i] = father[father[x][i-1]][i-1] ;
}
for ( int i = head[x] ; i ; i = nex[i] ) {
if ( to[i] == fa ) continue ;
dfs ( to[i] , x , depth + 1 ) ;
}
}
int LCA ( int x , int y ) {
if ( dep[x] < dep[y] ) swap ( x , y ) ;
for ( int i = 19 ; i >= 0 ; i -- ) {
if ( dep[father[x][i]] >= dep[y] ) {
x = father[x][i] ;
}
}
if ( x == y ) return x ;
for ( int i = 19 ; i >= 0 ; i -- ) {
if ( father[x][i] != father[y][i] ) {
x = father[x][i] , y = father[y][i] ;
}
}
return father[x][0] ;
}
int main ( ) {
scanf ( "%d%d%d" , & n , & m , & s ) ;
for ( int i = 1 ; i < n ; i ++ ) {
int x , y ; scanf ( "%d%d" , & x , & y ) ;
add ( x , y ) ; add ( y , x ) ;
}
dfs ( s , 0 , 1 ) ;
while ( m -- ) {
int x , y ; scanf ( "%d%d" , & x , & y ) ;
printf ( "%d\n" , LCA ( x , y ) ) ;
}
}
|
