Esimerkkikoodi

#include <iostream>
#include <vector>
#include <set>
using namespace std;
 
const int N = 100000;
 
vector<int> g[N];
set<int> queries[N];
int ans[N];
 
void dfs(int i, int p) {
	for (int j : g[i]) {
		if (j == p) continue;
 
		dfs(j, i);
 
		if (queries[j].size() > queries[i].size())
			swap(queries[i], queries[j]);
 
		for (int q_i : queries[j]) {
			if (queries[i].count(q_i)) {
				ans[q_i] = i;
				queries[i].erase(q_i);
			} else {
				queries[i].insert(q_i);
			}
		}
	}
}
 
int main() {
	int n, q;
	cin >> n >> q;
 
	for (int i = 0; i < n - 1; ++i) {
		int a, b;
		cin >> a >> b;
		a--;
		b--;
		g[a].push_back(b);
		g[b].push_back(a);
	}
 
	for (int i = 0; i < q; ++i) {
		int a, b;
		cin >> a >> b;
		a--;
		b--;
		if (a == b) {
			ans[i] = a;
		} else {
			queries[a].insert(i);
			queries[b].insert(i);
		}
	}
 
	dfs(0, 0);
 
	for (int i = 0; i < q; ++i) {
		cout << ans[i] + 1 << '\n';
	}
}