求解

#include <iostream>
#include <cmath>
#include <vector>
using namespace std;
int n, m, s, u, v, i, e[500010][25],b[500010];
vector<int> f[500010];
void dfs(int x, int fa) {
	b[x] = b[fa] + 1;
	e[x][0] = fa;
	for (int i = 1; i <= 20; i++) e[x][i] = e[e[x][i - 1]][i - 1];
	for (int i = 0; i < f[x].size(); i++)
		if (f[x][i] != fa) dfs(f[x][i], x);
}
int lca(int x, int y) {
	if (b[x] < b[y]) swap(x, y);
	int h = b[x] - b[y];
	for (int i = 20; i >= 0; i--)
		if (h & (1 << i)) x = e[x][i];
	if (x == y) return x;
	for (int i = 0; i <= 20; i++)
		if (e[x][i] != e[y][i]) x = e[x][i], y = e[y][i];
	return e[x][0];
}
int main() {
	cin >> n >> m >> s;
	for (i = 1; i < n; i++) cin >> u >> v, f[u].push_back(v), f[v].push_back(u);
	dfs(s, 0);
	while (m--) {
		cin >> u >> v;
		cout << lca(u, v)<<"\n";
	}
}