满江红求调0

#include<bits/stdc++.h>
using namespace std;
const int N=6e5+10,M=N*2;
int h[N],e[M],ne[M],idx;
int depth[N],fa[N][30];
int n,m;
void add(int a,int b){
    e[idx]=b,ne[idx]=h[a],h[a]=idx++;
}
void bfs(int root){
    memset(depth,0x3f,sizeof depth);
    queue<int> q;
    q.push(root);
    depth[0]=0,depth[root]=1;
    while(q.size()){
        int t=q.front();
        q.pop();
        for(int i=h[t];i!=-1;i=ne[i]){
            int j=e[i];
            if(depth[j]>depth[t]+1){
                depth[j]=depth[t]+1;
                fa[j][0]=t;
                q.push(j);
                for(int k=1;k<=30;k++)
                    fa[j][k]=fa[fa[j][k-1]][k-1];
            }
        }
    }
}
int lca(int a,int b){
    if(depth[a]<depth[b]) swap(a,b);
    for(int k=30;k>=0;k--)
        if(depth[fa[a][k]]>=depth[b])
            a=fa[a][k];
    if(a==b) return a;
    for(int k=30;k>=0;k--)
        if(fa[a][k]!=fa[b][k]){
            a=fa[a][k];
            b=fa[b][k];
        }
   	return fa[a][0];
}
int main()
{
    int root=0;
    cin>>n>>m>>root;
    memset(h,-1,sizeof h);
    for(int i=0;i<n-1;i++){
        int a,b;
        cin>>a>>b;
        add(a,b),add(b,a);
    }
    bfs(root);//预处理
    for(int i=0;i<m;i++){
        int a,b;
        cin>>a>>b;
        int p=lca(a,b);
        cout<<p<<endl;
    }
    return 0;
}