// Problem: P3379 【模板】最近公共祖先（LCA）
// Contest: Luogu
// URL: https://www.luogu.com.cn/problem/P3379
// Memory Limit: 512 MB
// Time Limit: 2000 ms
// 
// Powered by CP Editor (https://cpeditor.org)

#include <bits/stdc++.h>
#define int long long
using namespace std;
const int N = 500010;
int n , m , k , x , y , fa[N][30] , lg[N] , d[N];
vector <int> v[N];
void build (int id , int f) {
	fa[id][0] = f; d[id] = d[f] + 1;
	for  (int i = 1;i <= lg[d[id]];i ++) {
		fa[id][i] = fa[fa[id][i - 1]][i - 1];
	}
	for (int i = 0;i < v[id].size();i ++) {
		if (v[id][i] != f) {
			build (v[id][i] , id);
		}
	}
}
int LCA (int x , int y) {
	if (d[x] < d[y]) swap (x , y);
	while (d[x] > d[y]) {
		x = fa[x][lg[d[x] - d[y]] - 1];
	}
	if (x == y) return x;
	for (int i = lg[d[x]] - 1;i >= 0;i --) {
		if (fa[x][i] != fa[y][i]) {
			x = fa[x][i]; y = fa[y][i];
		}
	}
	return fa[x][0];
} 
signed main () {
	cin >> n >> m >> k;
	for (int i = 1;i < n;i ++) {
		cin >> x >> y;
		v[x].push_back (y);
		v[y].push_back (x);
	}
	for (int i = 1;i <= n;i ++) {
		lg[i] = lg[i - 1] + (1 << lg[i - 1] == i);
	}
	build (k , 0);
	while (m --) {
		cin >> x >> y;
		cout << LCA (x , y) << '\n';
	}
	
	return 0;
} 

提交记录