提交 7TLE 1WA

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

struct node{
	vector<int> con;
	int f,hson;
	int s;
	int depth;
	int w;
}tr[500010];
int n,t=1,m,root;

void init(int p){//Get father depth weight and heavest son
	int w=0;
	tr[p].w=1;
	for(int q:tr[p].con){
		if(q!=tr[p].f){
			tr[q].f=p,tr[q].depth=tr[p].depth+1;
			init(q);
			tr[p].w+=tr[q].w;
			if(tr[q].w>w)tr[p].hson=q,w=tr[q].w;
		}
	}
}

void heavyedge(int p){//Get chain's top
	if(tr[tr[p].f].hson==p)
		tr[p].s=tr[tr[p].f].s;
	else
		tr[p].s=p;
	if(tr[p].con.size()!=1){
		heavyedge(tr[p].hson);
		for(int q:tr[p].con){
			if(q!=tr[p].hson&&q!=tr[p].f)
				heavyedge(q);
		}
	}
}

int search(int u,int v){
	while(tr[u].s!=tr[v].s){
		if(tr[tr[u].s].depth<tr[tr[v].s].depth)swap(u,v);
		u=tr[tr[u].s].f;
	}
	return tr[u].depth<tr[v].depth?u:v;
}

// F-IO
void read(int &res){
	res=0;
	char c=getchar();int f=1;
	while(c<48||c>57){if(c=='-')f=-1;c=getchar();}
	while(c>47&&c<58)res=(res<<3)+(res<<1)+(c^48),c=getchar();
	res*=f;
} 
void write(int a){
	if(!a){putchar('0');putchar('\n');return;}
	if(a<0){putchar('-');a=-a;}
	int l=0;
	char c[50];
	while(a){c[++l]=(a%10)^48;a/=10;}
	while(l)putchar(c[l--]);
	putchar('\n');
}

int main(){
	read(n);read(m);read(root);//Input
	for(int i=1;i<n;i++){
		int u,v;
		read(u);read(v);
		tr[u].con.push_back(v);
		tr[v].con.push_back(u);
	}
	
	//Init
	tr[root].depth=1;
	init(root);
	heavyedge(root);
	tr[root].f=root;
	
	//Solve
	while(m--){
		int u,v;
		read(u);read(v);
		write(search(u,v));
	}
	return 0;
}