LCA

LCA

#include<bits/stdc++.h> using namespace std; inline long long read(){ long long num=0;int z=1;char c=getchar(); if(c=='-') z=-1; while((c<'0'||c>'9')&&c!='-') c=getchar(); if(c=='-') z=-1,c=getchar(); while(c>='0'&&c<='9') num=(num<<1)+(num<<3)+(c^48),c=getchar(); return z*num; } int m,n,s,tot; struct a{ int v,next; }e[500005*2]; int head[500005],d[500005],fa[500005][24]; void add(int x,int y) { tot++; e[tot].v=y; e[tot].next=head[x]; head[x]=tot; } void dfs(int x,int y) { d[x]=d[y]+1; fa[x][0]=y; for(int i=1;i<=19;i++) { fa[x][i]=fa[fa[x][i-1]][i-1]; } for(int i=head[x];i;i=e[i].next) { int c=e[i].v; if(c==y)continue; dfs(c,x); } } int ask(int x,int y) { if(d[x]>d[y])swap(x,y); for(int i=20;i>=0;i--) { if(d[x]<=d[y]-(1<<i)) { y=fa[y][i]; } } if(x==y)return x; for(int i=20;i>=0;i--) { if(fa[x][i]==fa[y][i]) { continue; } else{ x=fa[x][i];y=fa[y][i]; } } return fa[x][0]; } int main(){ n=read();m=read();s=read(); for(int i=1;i<=n-1;i++) { int x,y; x=read();y=read(); add(x,y);add(y,x); } dfs(s,0); for(int i=1;i<=m;i++) { int a,b; a=read();b=read(); printf("%d\n",ask(a,b)); } return 0; }