dfs序上两点之间深度最小的点就是最近公共祖先节点，用rmq在深度数组求区间最值即可
//#pragma GCC optimize(3,"Ofast","inline") #include<unordered_map> //#include<unordered_set> #include<cstdio> #include<iostream> #include<cmath> #include<functional> #include<cstring> #include<string> #include<cstdlib> #include<queue> #include<map> #include<algorithm> #include<set> #include<stack> #include<vector> #include<sstream> #include<list> using namespace std; typedef long long ll; const int INF=0x3f3f3f3f; int mod=1000000007; const int N=2e3+10; const int maxn=5e5+7; int num; int f[2*maxn][25],d[maxn],vis[maxn],head[maxn],id[maxn],dfsx[2*maxn]; int n,m,root; struct node { int to,next; } p[2*maxn]; void add(int from,int to) { p[num].to=to; p[num].next=head[from]; head[from]=num++; } void dfs(int x,int ceng) { dfsx[num]=x; id[x]=num; d[x]=ceng; num++; vis[x]=1; for(int i=head[x]; i!=-1; i=p[i].next) if(!vis[p[i].to]) { dfs(p[i].to,ceng+1); dfsx[num]=x; num++; } } void rmq() { for(int i=1; i<=num; i++)f[i][0]=dfsx[i]; for(int j=1; (1<<j)<=num; j++) for(int i=1; i+(1<<j)-1<=num; i++) { if(d[f[i][j-1]]<d[f[i+(1<<j-1)][j-1]])f[i][j]=f[i][j-1]; else f[i][j]=f[i+(1<<j-1)][j-1]; } } int lca(int x,int y) { if(id[x]>id[y])swap(x,y); int len=id[y]-id[x]+1; int cnt=0,ans=1; while(ans<=len) { cnt++; ans<<=1; } cnt--; ans>>=1; if(d[f[id[x]][cnt]]<d[f[id[y]-ans+1][cnt]]) return f[id[x]][cnt]; else return f[id[y]-ans+1][cnt]; } int main() { memset(head,-1,sizeof head); cin>>n>>m>>root; int x,y; for(int i=1; i<n; i++) { cin>>x>>y; add(x,y); add(y,x); } num=1; dfs(root,0); num--; rmq(); while(m--) { cin>>x>>y; cout<<lca(x,y)<<endl; } return 0; }