rt, Tarjan写的。

#include<bits/stdc++.h>
using namespace std;
const int N = 5 * 1e5 + 10;
struct edge{
    int v, next;
}e[2 * N];//邻接表存图
int h[N], etot, n, s;
void add_edge(int u, int v){
    e[etot] = (edge){v, h[u]};
    h[u] = etot++;
}
struct query{
    int v, next, id;
}q[2 * N];//存询问
int Q[N], qtot, ans[N];
void add_query(int u, int v, int id){
    q[qtot] = (query){v, Q[u], id};
    Q[u] = qtot++;
}
int f[N];
void make_set(int x){//并查集
    f[x] = x;
} 
int find_set(int x){
    return (f[x] == x) ? f[x] : find_set(f[x]);
}
bool Union(int x, int y){
    x = find_set(x);
    y = find_set(y);
    if(x == y) return 0;
    f[x] = y;
    return 1;
}
bool vis[N];
void Tarjan(int u, int fa){
    for(int i = h[u]; i != -1; i = e[i].next){
        int v = e[i].v;
        if(v == fa) continue;
        Tarjan(v, u);
        if(Union(v, u)) vis[v] = 1;
        else puts("*");
    }
    for(int i = Q[u]; i != -1; i = q[i].next){
        int v = q[i].v;
        if(vis[v]){
            ans[q[i].id] = find_set(v);
        }
    }
}
int m;
int main(){
    memset(h, -1, sizeof(h));
    memset(Q, -1, sizeof(Q));
    scanf("%d%d%d", &n, &m, &s);
    for(int i = 1; i <= n; i++) make_set(i);
    int u, v;
    for(int i = 1; i <= n - 1; i++){
        scanf("%d%d", &u, &v);
        add_edge(u, v);
        add_edge(v, u);
    }
    for(int i = 1; i <= m; i++){
        scanf("%d%d", &u, &v);
        if(u == v){
            ans[i] = u;
            continue;
        }
        add_query(u, v, i);
        add_query(v, u, i);
    }
    Tarjan(s, 0);
    for(int i = 1; i <= m; i++){
        printf("%d\n", ans[i]);
    }
    return 0;
}