题目传送门

感觉和老师上课讲的方法一样，自己写的时候改了一点，结果测试数据爆了一个T，HACK全部爆T，我是不是改的太暴力了

#include <bits/stdc++.h>
using namespace std;
int n,m,s,x,y,a,b;
vector <int> T[500005];
int f[500005][20];//f[i][j]表示i的第2^j个父亲是谁
//f[i][j]=f[f[i][j-1]][j-1]
int deep[500005];
void dfs(int x){
	for (int i = 0;i < 20;i++){
		if (f[x][i-1]) f[x][i] = f[f[x][i-1]][i-1];
		else break;
	}
	for (int i = 0;i < T[x].size();i++){
		if (T[x][i] == f[x][0]) continue;
		f[T[x][i]][0] = x;
		deep[T[x][i]] = deep[x] + 1;
		dfs(T[x][i]);
	}
}
int LCA(int u,int v){//u=v 
	if (u == v) return v;
	return LCA(f[u][0],f[v][0]);
}
int main(){
	cin >> n >> m >> s;
	for (int i = 1;i < n;i++){
		int x,y;
		cin >> x >> y;
		T[x].push_back(y);
		T[y].push_back(x);
	}
	deep[s] = 0;
	dfs(s);
	while (m--){
		int a,b;
		cin >> a >> b;
		int u = a,v = b;
		if (deep[u] > deep[v]) swap(u,v);
		while (deep[u] - deep[v]) v = f[v][0];
		cout << LCA(u,v) << endl;
	}
	return 0;
}