在别的地方时限1.5s空间限制256M跑的比洛谷慢还没开O2都能AC，到洛谷这儿全部MLE了。

#include <bits/stdc++.h>
using namespace std;
int n,m,s,p[500005],dep[500005],p1[500005][20];
vector<int> g[500005],t[500005];
void dfs(int x,int fa,int dp)
{
	dep[x] = dp;
	for(auto it:g[x])
	{
		if(it == fa)continue;
		p[it] = x;
		dfs(it,x,dp+1);
	}
}
void init()
{
	for(int i = 1;i <= n;i++)
	{
		p1[i][0] = p[i];
	}
	for(int t = 1;t <= 19;t++)
	{
		for(int i = 1;i <= n;i++)
		{
			p1[i][t] = p1[p1[i][t-1]][t-1];
		}
	}
}
int djzx(int x,int d)
{
	int pa = x,cnt = 0;
	while(d)
	{
		if(d & 1)pa = p1[pa][cnt];
		d >>= 1;
		cnt++;
	}
}
int lca(int a,int b)
{
	if(dep[a] < dep[b])swap(a,b);
	a = djzx(a,dep[a]-dep[b]);
	if(a == b)
	{
		return a;
	}
	int pos = 19,ans = 0;
	for(int i = 19;i >= 0;i--)
	{
		if(p1[a][i] != p1[b][i])
		{
			ans += 1<<i;
			a = p1[a][i];
			b = p1[b][i];
		}
	}
	a = p[a];
	return a;
}
int main()
{
	ios::sync_with_stdio(0);
	cin.tie(0);
	cout.tie(0);
	cin >> n >> m >> s;
	for(int i = 1;i < n;i++)
	{
		int x,y;
		cin >> x >> y;
		g[x].push_back(y);
		g[y].push_back(x);
	}
	dfs(s,0,1);
	init();
	while(m--)
	{
		int a,b;
		cin >> a >> b;
		cout << lca(a,b) << "\n";
	}
	return 0;
}