rt,怀疑是tarjan写假了， 数剖1.5s, tarjan2.8s

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

const int N = 1e6 + 10;
int fa[N], n, m, s;
bool vis[N];
int ans[N];
vector<int> vec[N];
struct query{
	int v, id;
};
vector<query> que[N];
inline void add(int u, int v) { vec[u].push_back(v); }
inline void addq(int u, int v, int id) { que[u].push_back({v, id}); }
void read() {
	cin >> n >> m >> s;
	int u, v;
	for (int i = 1; i <= n - 1; i++) {
		scanf("%d %d", &u, &v);
		add(u, v);
		add(v, u);
	}
	for (int i = 1; i <= m; i++) {
		scanf("%d %d", &u, &v);
		addq(u, v, i);
		addq(v, u, i);
	}
} 
inline int find(int x) { return x == fa[x] ? x : fa[x] = find(fa[x]); }
void dfs(int u) {
	fa[u] = u;
	vis[u] = 1;
	int v;
	for (int i = 0; i < vec[u].size(); i++) {
		v = vec[u][i];
		if (vis[v])
			continue;
		dfs(v);
		fa[v] = u;
	}
	for (int i = 0; i < que[u].size(); i++) {
		v = que[u][i].v;
		if (!vis[v])
			continue;
		ans[que[u][i].id] = find(v);
	}
}
int main() {
	read();
	dfs(s);
	for (int i = 1; i <= m; i++)
		printf("%d\n", ans[i]);
	return 0; 
}