#include<bits/stdc++.h>

using namespace std;

const int MAXN=1000001;

int Log[MAXN];
int f[MAXN][31];
int depth[MAXN];
int head[MAXN],pre[MAXN],ver[MAXN];
int cnt=1;

int n,m,s;

inline int read()
{
    char ch=getchar();
    int x=0;
    while(ch>'9'||ch<'0') ch=getchar();
    while(ch<='9'&&ch>='0')
    {
        x=x*10+ch-'0';
        ch=getchar();
    }
    return x;
}

void add_edge(int u,int v)
{
    pre[cnt]=head[u];
    head[u]=cnt;
    ver[cnt]=v;
    cnt++;
}

void dfs(int st,int fno)
{
    depth[st]=depth[fno]+1;
    f[st][0]=fno;
    for(int i=1;i<=Log[n];i++) f[st][i]=f[f[st][i-1]][i-1];
    for(int i=head[st];i;i=pre[i])
    {
        if(ver[i]==fno) continue;
        dfs(ver[i],st);
    }
    return;
}

int lca(int x,int y)
{
    if(depth[x]>depth[y]) swap(x,y);
    int tmp=depth[y]-depth[x];
    for(int j=0;tmp;j++,tmp>>=1)
    {
        if(tmp&1) y=f[y][j];
    }
    if(x==y) return x;
    for(int i=Log[n];i>=0;i--)
    {
        if(f[x][i]!=f[y][i])
        {
            x=f[x][i];
            y=f[y][i];
        }
    }
    return f[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_edge(x,y);
        add_edge(y,x);
    }
    int rot=s;
    Log[1]=0,Log[2]=1;
    for(int i=3;i<=n;i++) Log[i]=Log[i/2]+1;
    dfs(rot,0);
    for(int i=1;i<=m;i++)
    {
        int x,y;
        x=read(),y=read();
        cout<<lca(x,y)<<endl;
    }
    return 0;
}

这份代码十个点一共跑了5s

怎么卡下常，最慢的一个点985ms，我觉得我比较危