LCA

``` #include<iostream> #include<cstdio> #include<cmath> using namespace std; int ans[500001][20]; int deep[500001]; int head[500001]; int n,m,s,cnt; struct edge{ int next,to; }a[1000001]; void add(int x,int y) { cnt++; a[cnt].next=head[x]; a[cnt].to=y; head[x]=cnt; } void dfs(int now,int x) { for(int i=head[now];i;i=a[i].next) { if(a[i].to==x)continue; deep[a[i].to]=deep[now]+1; dfs(a[i].to,now); ans[a[i].to][0]=now; } } int lca(int x,int y) { if(deep[x]<deep[y])swap(x,y); int pp=floor(log(n)/log(2)); for(int i=pp;i>=0;i--) if(deep[x]-(1<<i)>=deep[y])x=ans[x][i]; if(x==y)return y; for(int i=pp;i>=0;i--) if(ans[x][i]!=ans[y][i]) { x=ans[x][i]; y=ans[y][i]; } return ans[x][0]; } int main() { scanf("%d%d%d",&n,&m,&s); int x,y; for(int i=1;i<=n-1;i++) { scanf("%d%d",&x,&y); add(x,y); add(y,x); } dfs(s,s); for(int i=1;(1<<i)<=n;i++) for(int j=1;j<=n;j++) ans[j][i]=ans[ans[j][i-1]][i-1]; for(int i=1;i<=m;i++) { int x,y; scanf("%d%d",&x,&y); printf("%d\n",lca(x,y)); } } ```