重链剖分0分求条

#include<bits/stdc++.h>
using namespace std;
const int N=500005;
int n,m,k,dep[N],fa[N],siz[N],top[N],hson[N];
vector<int> v[N];
int rdfs(int father,int now){
	fa[now]=father;
	dep[now]=dep[father]+1;
	int all=0,ma=0,d=0;
	for(auto it=begin(v[now]);it!=end(v[now]);it++){
		if(*it!=father){
			int x=rdfs(now,*it);
			all+=x;
			if(x>ma){
				ma=x;
				d=*it;
			}
		}
	}
	all++;
	hson[now]=d;
	siz[now]=all;
	return all;
}
void ftop(int root,int father,int now){
	top[now]=root;
	ftop(root,now,hson[now]);
	for(auto it=begin(v[now]);it!=end(v[now]);it++){
		if(*it!=father&&*it!=hson[now]){
			ftop(*it,now,*it);
		}
	}
}
int main(){
	cin>>n>>m>>k;
	for(int i=1;i<n;i++){
		int x,y;
		cin>>x>>y;
		v[x].push_back(y);
		v[y].push_back(x);
	}
	rdfs(0,k);
	ftop(k,0,k);
	while(m--){
		int x,y;
		cin>>x>>y;
		while(top[x]!=top[y]){
			if(dep[x]<dep[y])x=fa[top[x]];
			else y=fa[top[y]];
		}
		if(dep[x]<dep[y])cout<<x<<endl;
		else cout<<y<<endl;
	}
	return 0;
}