//详解见https://www.cnblogs.com/zwfymqz/p/7795299.html
//博主： 自为风月马前卒 https://www.cnblogs.com/zwfymqz/
// 洛谷 P3379 最近公共祖先 链接https://www.luogu.org/problem/P3379
1 #include<cstdio> 2 #include<cstring> 3 #include<algorithm> 4 using namespace std; 5 6 const int MAXN = 1e5+10; 7 8 struct node { 9 int v, next; 10 } edge[MAXN]; 11 12 int head[MAXN]; 13 int num = 1; 14 inline void add_edge(int x, int y) { 15 edge[num].v = y; 16 edge[num].next = head[x]; 17 head[x] = num++; 18 } 19 20 int f[MAXN][21]; 21 int deep[MAXN]; 22 int n, m, root; 23 void dfs(int cur) { 24 for(int i = head[cur]; i != -1; i = edge[i].next) { 25 if(!deep[edge[i].v]) { 26 deep[edge[i].v] = deep[cur] + 1; 27 f[edge[i].v][0] = cur; 28 dfs(edge[i].v); 29 } 30 } 31 } 32 33 void PRE() { 34 for(int j = 1; j <= 19; ++j) { 35 for(int i = 1; i <= n; ++i) { 36 f[i][j] = f[f[i][j-1]][j-1]; 37 } 38 } 39 } 40 41 int LCA(int x, int y) { 42 if(deep[x] < deep[y]) swap(x, y); 43 for(int i = 19; i >= 0; --i) { 44 if(deep[f[x][i]] >= deep[y]) { 45 x = f[x][i]; 46 } 47 } 48 if(x == y) return x; 49 for(int i = 19; i >= 0; --i) { 50 if(f[x][i] != f[y][i]) { 51 x = f[x][i]; 52 y = f[y][i]; 53 } 54 } 55 return f[x][0]; 56 } 57 58 int main() { 59 memset(head, -1, sizeof(head)); 60 scanf("%d%d%d", &n, &m, &root); 61 int x, y; 62 for(int i = 0; i != n-1; ++i) { 63 scanf("%d%d", &x, &y); 64 add_edge(x, y); 65 add_edge(y, x); 66 } 67 deep[root] = 1; 68 dfs(root); 69 PRE(); 70 for(int i = 0; i != n; ++i) { 71 scanf("%d%d", &x, &y); 72 printf("%d\n", LCA(x, y)); 73 } 74 return 0; 75 }