Tarjan LCA 本机无事 提交全紫 求条

#include <iostream>
#include <vector>
using namespace std;

const int MAXN = 5e5 + 1;

int n, m, s, fa[MAXN], qa[MAXN], qb[MAXN], ans[MAXN];
vector<int> dic[MAXN], g[MAXN];
bool vis[MAXN];

int find(int x){return fa[x] ? fa[x] = find(fa[x]) : x;}
int merge(int x, int y){fa[find(x)] = find(y);}

void tarjan(int u, int f){
	vis[u] = true;
	for (int v : g[u]){
		if (v == f) continue;
		tarjan(v, u);
		merge(v, u);
	}
	for (int v : dic[u]){
		if (qa[v] == qb[v]) ans[v] = u;
		if (vis[qa[v]] && vis[qb[v]]){
			if (qa[v] == u) ans[v] = find(qb[v]);
			else ans[v] = find(qa[v]);
		}
	}
}

int main(){
	cin >> n >> m >> s;
	for (int i = 1; i < n; i++){
		int x, y;
		cin >> x >> y;
		g[x].push_back(y);
		g[y].push_back(x);
	}
	for (int i = 1; i <= m; i++){
		int a, b;
		cin >> a >> b;
		qa[i] = a, qb[i] = b;
		dic[a].push_back(i);
		dic[b].push_back(i);
	}
	
	tarjan(s, 0);
	
	for (int i = 1; i <= m; i++){
		cout << ans[i] << '\n';
	}
	
	return 0;
}