（模板）LCA

```cpp #include<bits/stdc++.h> using namespace std; const int N=500001; int head[N],deep[N],ans[N][23]; int n,m,s,cnt; template <class sjy> inline void read(sjy &x){ sjy f=1;x=0;char ch=getchar(); while(ch<'0'||ch>'9'){if(ch=='-')f=-1;ch=getchar();} while(ch>='0'&&ch<='9'){x=(x<<3)+(x<<1)+ch-'0';ch=getchar();} x*=f; } struct edge{ int to,next; }a[N<<1]; void add(int x,int y){ a[++cnt].next=head[x]; a[cnt].to=y; head[x]=cnt; } void dfs(int now,int from){ for(int i=head[now];i;i=a[i].next){ int v=a[i].to; if(v==from) continue; deep[v]=deep[now]+1; dfs(v,now); ans[v][0]=now; } } int lca(int x,int y){ if(deep[x]<deep[y]) swap(x,y); for(int i=22;i>=0;i--) if(deep[x]-(1<<i)>=deep[y]) x=ans[x][i]; if(x==y) return x; for(int i=22;i>=0;i--) if(ans[x][i]!=ans[y][i]){ x=ans[x][i]; y=ans[y][i]; } return ans[x][0]; } int main(){ int x,y; read(n),read(m),read(s); for(int i=1;i<n;i++){ read(x),read(y); add(x,y);add(y,x); } dfs(s,s); for(int i=1;i<=22;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++){ read(x),read(y); printf("%d\n",lca(x,y)); } } ```