用map做的100分，#1 TLE，改了前向星直接60分

#include <algorithm>
#include <cstdint>
#include <iostream>
#include <limits>
#include <set>
#include <map>
#include <vector>

using namespace std;

int n,m,s;
constexpr int maxEdge=500010;
struct Edge{
    int to,next;
}E[maxEdge];
int countEdge,Head[maxEdge];
void addEdge(int u,int v){
    E[countEdge].to=v;
    E[countEdge].next=Head[u];
    Head[u]=countEdge;
    ++countEdge;
}

int f[500010][25];
int dep[500010];
int tot;

void dfs(int x,int p){
    dep[x]=dep[p]+1;
    for(int i=1;(1<<i)<=dep[x];++i){
        f[x][i]=f[f[x][i-1]][i-1];
    }
    for(int i=Head[x];i;i=E[i].next){
        if(E[i].to==p){
            continue;
        }
        f[E[i].to][0]=x;
        dfs(E[i].to,x);
    }
}

int lca(int x,int y){
    if(dep[x]<dep[y]){
        swap(x,y);
    }
    for(int i=20;i>=0;--i){
        if(dep[f[x][i]]>=dep[y]){
            x=f[x][i];
        }
        if(x==y){
            return x;
        }
    }
    for(int i=20;i>=0;--i){
        if(f[x][i]!=f[y][i]){
            x=f[x][i];
            y=f[y][i];
        }
    }
    return f[x][0];
}

int main()
{
    cin.tie(nullptr);
    ios::sync_with_stdio(false);
    cin>>n>>m>>s;
    for(int i=1;i<=n-1;++i){
        int u,v;
        cin>>u>>v;
        adj[u].insert(v);
        adj[v].insert(u);
        addEdge(u,v);
        addEdge(v,u);
    }
    dfs(s,0);
    for(int i=1;i<=m;++i){
        int a,b;
        cin>>a>>b;
        cout<<lca(a,b)<<'\n';
    }
}

用map的如下

#include <algorithm>
#include <cstdint>
#include <iostream>
#include <limits>
#include <set>
#include <map>
#include <vector>

using namespace std;

int n,m,s;
map<int,set<int>> adj;

int f[500010][25];
int dep[500010];
int tot;

void dfs(int x,int p){
    dep[x]=dep[p]+1;
    for(int i=1;(1<<i)<=dep[x];++i){
        f[x][i]=f[f[x][i-1]][i-1];
    }
    for(auto i:adj[x]){
        if(i==p){
            continue;
        }
        f[i][0]=x;
        dfs(i,x);
    }
}

int lca(int x,int y){
    if(dep[x]<dep[y]){
        swap(x,y);
    }
    for(int i=20;i>=0;--i){
        if(dep[f[x][i]]>=dep[y]){
            x=f[x][i];
        }
        if(x==y){
            return x;
        }
    }
    for(int i=20;i>=0;--i){
        if(f[x][i]!=f[y][i]){
            x=f[x][i];
            y=f[y][i];
        }
    }
    return f[x][0];
}

int main()
{
    cin.tie(nullptr);
    ios::sync_with_stdio(false);
    cin>>n>>m>>s;
    for(int i=1;i<=n-1;++i){
        int u,v;
        cin>>u>>v;
        adj[u].insert(v);
        adj[v].insert(u);
    }
    dfs(s,0);
    for(int i=1;i<=m;++i){
        int a,b;
        cin>>a>>b;
        cout<<lca(a,b)<<'\n';
    }
}