#include<bits/stdc++.h> 
using namespace std;
const int MAXN=600005;
const int MAXD=30;
int head[MAXN];
struct edge{
	int s,e,next;
}eg[MAXN*2];
int cot=1;
int a[MAXN*2],s[MAXN],cnt;
int st[MAXN*2][MAXD],deep[MAXN];
int n,m,S;
void addedge(int s,int e){
	eg[cot].s=s;
	eg[cot].e=e;
	eg[cot].next=head[s];
	head[s]=cot++;
}
void DFS(int x){
	a[++cnt]=x;
	s[x]=cnt;
	for(int i=head[x];i!=-1;i=eg[i].next){
		int to=eg[i].e;
        if(!deep[to]){
    		deep[to]=deep[x]+1;
    		DFS(to);
    		a[++cnt]=x;
        }
	}
}
int deep_min(int x,int y){
	return (deep[x]<deep[y]?x:y);
}
void build_ST(){
	for(int i=1;i<=cnt;i++)st[i][0]=a[i];
	for(int j=1;(1<<j)<=cnt;j++)
		for(int i=1;i+(1<<j)-1<=cnt;i++)
			st[i][j]=deep_min(st[i][j-1],st[i+(1<<(j-1))][j-1]);
}
int LCA(int x,int y){
	int l=s[x],r=s[y];
	if(l>r)swap(l,r);
	int k=(int)(log(r-l+1)/log(2));
	return deep_min(st[l][k],st[r-(1<<k)+1][k]);
}
int main(){
	memset(head,-1,sizeof(head));
	cin>>n>>m>>S;
	for(int i=1;i<n;i++){
		int a,b;
		cin>>a>>b;
		addedge(a,b);
		addedge(b,a);
	}
	deep[S]=1;
	DFS(S);
	build_ST();
	for(int i=1;i<=n;i++){
		int x,y;
		cin>>x>>y;
		cout<<LCA(x,y)<<endl;
	}
	return 0;
}

测试点13是Wrong Answer.wrong answer Too short on line 499992.

测试点14是Wrong Answer.wrong answer Too long on line 499996.

提交记录

有没有大佬帮忙看看