如下

#include <iostream>
#include <vector>

using std::cin;
using std::cout;
using std::endl;
using std::vector;

class LCA
{
	/*
	* 最近公共祖先算法
	*/
public:
#define MAX_SIZE 1000100

	vector<int> edge[MAX_SIZE];	/*边*/
	int key[MAX_SIZE];	/*关键字*/
	int visit[MAX_SIZE];	/*访问标志*/
	int f[MAX_SIZE];	/*公共祖先*/
	vector<int> connect[MAX_SIZE];	/*联系对象*/
	int ans[MAX_SIZE];	/*答案*/
	vector<int> ON[MAX_SIZE];	/*对应结点的编号*/

	int root;	/*根结点*/

	int find(int x);	/*Tarjan查询公共祖先*/
	void Tarjan(int p, int pa);	/*Tarjan算法（离线）*/
};

int LCA::find(int x)
{
	/*
	* 查找公共祖先
	*/

	int p = x;
	while (f[p] != p)
		p = f[p];
	return p;
}

void LCA::Tarjan(int p, int pa)
{
	/*
	* Tarjan算法
	* 离线
	*/
	
	/*标记已找到*/
	visit[p] = 1;

	/*遍历儿子*/
	for (int i = 0; i < edge[p].size(); i++)
	{
		if (!visit[edge[p][i]])
			Tarjan(edge[p][i], p);
	}

	/*找有关系的结点*/
	for (int i = 0; i < connect[p].size(); i++)
	{
		if (visit[connect[p][i]] == 2)
			ans[ON[p][i]] = find(connect[p][i]);
	}

	/*无儿子和有关的结点，标记*/
	visit[p] = 2;
	f[p] = pa;
}

LCA lca;

int main()
{
	int n, m, s;
	cin >> n >> m >> s;
	lca.root = s;
	for (int i = 0; i < n; i++)
		lca.visit[i] = 0, lca.f[i] = i;
	for (int i = 0; i < n - 1; i++)
	{
		int x, y;
		cin >> x >> y;
		lca.edge[x].push_back(y);
		lca.edge[y].push_back(x);
	}
	for (int i = 0; i < m; i++)
	{
		int x, y;
		cin >> x >> y;
		lca.connect[x].push_back(y);
		lca.connect[y].push_back(x);
		lca.ON[x].push_back(i);
		lca.ON[y].push_back(i);
	}
	lca.Tarjan(lca.root, lca.root);

	for (int i = 0; i < m; i++)
		cout << lca.ans[i] << endl;

	return 0;
}