luogu
#include<iostream> #include<cstdio> #include<algorithm> #include<cstring> #include<string> #include<cmath> #include<vector> #define NN 500000 using namespace std; int n,m,s; //vector <int> a[NN+2]; int num[2*NN+9],head[NN+9],nxt[2*NN+9],cnt=0; int p[NN+2][20],deep[NN+2];//p[i][j]表示i节点往上跳2^j次到达的父亲 inline int Read(){ int x=0,f=1;char c=getchar(); while(c>'9'||c<'0') {if(c=='-') f=-1;c=getchar();} while(c>='0'&&c<='9') {x=x*10+c-'0'; c=getchar();} return x*f; } void dfsfa(int u) { for(int i=head[u];i;i=nxt[i]) if(!p[num[i]][0]){ int x=num[i]; p[x][0]=u; deep[x]=deep[u]+1; dfsfa(x); } } void fa2() { for(int j=1;(1<<j)<=n;j++) for(int i=1;i<=n;i++) if(p[i][j-1]!=-1){ p[i][j]=p[p[i][j-1]][j-1]; } } int LCA(int a,int b) { if(deep[a]<deep[b])swap(a,b); int x; for(x=0;(1<<x)<=deep[a];x++); x--; for(int j=x;j>=0;j--) if(deep[a]-(1<<j)>=deep[b]) a=p[a][j]; //a,b 到了同一高度 if(a==b)return a; for(int j=x;j>=0;j--){//找 if(p[a][j]!=-1&&p[a][j]!=p[b][j]) { a=p[a][j]; b=p[b][j]; } } return p[a][0]; } int main() { scanf("%d%d%d",&n,&m,&s); for(int i=1;i<=n-1;i++) { int x,y; x=Read(); y=Read(); //scanf("%d%d",&x,&y); cnt++; num[cnt]=x; nxt[cnt]=head[y]; head[y]=cnt; cnt++; num[cnt]=y; nxt[cnt]=head[x]; head[x]=cnt; } deep[s]=0;p[s][0]=-1; dfsfa(s); fa2(); for(int i=1;i<=m;i++){ int x,y; x=Read(); y=Read(); //scanf("%d%d",&x,&y); printf("%d\n",LCA(x,y)); } return 0; }