rt

TLE 11, 12

code:

#include<bits/stdc++.h>
using namespace std;
const int SIZE = 1000005;
int to, son[SIZE], dep[SIZE], siz[SIZE], fa[SIZE], tp[SIZE], id[SIZE], rev[SIZE];
//vector<int>v[2*SIZE];
struct node{
    int to, next;
}k[SIZE];
int head[SIZE], number;
inline void add(int x, int y){
    ++number;
    k[number].to = y;
    k[number].next = head[x];
    head[x] = number;
}
void dfs(int now, int f){
    siz[now] = 1;
    for(register int i = head[now]; ~i; i = k[i].next){
        to = k[i].to;
        if(to == f) continue;
        dep[to] = dep[now] + 1;
        fa[to] = now;
        dfs(to, now);
        siz[now] += siz[to];
        if(siz[to] > siz[son[now]]) son[now] = to;  
    }
}
void dfs2(int now){
    if(now == son[fa[now]])
        tp[now] = tp[fa[now]];
    else tp[now] = now;
    for(register int i = head[now]; ~i; i = k[i].next){
        if(k[i].to != fa[now]) dfs2(k[i].to);
    }
}
inline int LCA(int x, int y){
    while(tp[x] != tp[y]){
        if(dep[tp[x]] > dep[tp[y]])
            x = fa[tp[x]];
        else y = fa[tp[y]];
    }
    return dep[x] > dep[y]?y:x;
}
int main()
{
    int n, m, s, x, y;
	scanf("%d%d%d", &n, &m, &s);
    for(register int i = 1; i <= n - 1; i++){
        scanf("%d%d", &x, &y);
        add(x, y), add(y, x);
    }
    dfs(s, 0);
    dfs2(s);
    for(register int i = 1; i <= m; i++){
        scanf("%d%d", &x, &y);
        printf("%d\n", LCA(x, y));
    }
}