提交记录

#include<bits/stdc++.h>
using namespace std;

const int maxn = 5e5 + 6;
struct Edge
{
	int to, next;
}
edge[maxn << 1];
int head[maxn << 1], cnt;
int fa[maxn][20], dep[maxn];
int n, m, rt;

void init()
{
	for (int i = 0; i <= maxn << 1; i ++)
	{
		edge[i].next = -1;
		head[i] = -1;
	}
}

void addedge(int u, int v)
{
	edge[cnt].to   = v;
	edge[cnt].next = head[u];
	head[u]        = cnt ++;
}

int dfs(int x, int fat)
{
	dep[x] = dep[fat] + 1;
	fa[x][0] = fat;
	for (int i = 1; (1 << i) <= dep[x]; i ++)
	{
		fa[x][i] = fa[fa[x][i - 1]][i - 1];
	}
	for (int i = head[x]; ~i; i = edge[i].next)
	{
		if (edge[i].to != fat)
		{
			dfs(edge[i].to, x);
		}
	}
}

int LCA(int x, int y)
{
	if (dep[x] < dep[y])
	{
		swap(x, y);
	}
	for (int i = 19; i >= 0; i --)
	{
		if (dep[x] - (1 << i) >= dep[y])
		{
			x = fa[x][i];
		}
	}
	if (x == y)
	{
		return x;
	}
	for (int i = 19; i >= 0; i --)
	{
		if (fa[x][i] != fa[y][i])
		{
			x = fa[x][i];
			y = fa[y][i];
		}
	}
	return fa[x][0];
}

signed main()
{
	init();
	scanf("%d %d %d", &n, &m, &rt);
	for (int i = 1, u, v; i < n; i ++)
	{
		scanf("%d %d", &u, &v);
		addedge(u, v);
		addedge(v, u);
	}
	dfs(rt, 0);
	for (int i = 1, u, v; i <= m; i ++)
	{
		scanf("%d %d", &u, &v);
		printf("%d\n", LCA(u, v));
	}
	return 0;
}