最近公共祖先（LCA）

  1
  2
  3
  4
  5
  6
  7
  8
  9
 10
 11
 12
 13
 14
 15
 16
 17
 18
 19
 20
 21
 22
 23
 24
 25
 26
 27
 28
 29
 30
 31
 32
 33
 34
 35
 36
 37
 38
 39
 40
 41
 42
 43
 44
 45
 46
 47
 48
 49
 50
 51
 52
 53
 54
 55
 56
 57
 58
 59
 60
 61
 62
 63
 64
 65
 66
 67
 68
 69
 70
 71
 72
 73
 74
 75
 76
 77
 78
 79
 80
 81
 82
 83
 84
 85
 86
 87
 88
 89
 90
 91
 92
 93
 94
 95
 96
 97
 98
 99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129

#include<iostream>
#include<cstring>
#include<cstdio>
#include<cstdlib>
using namespace std;
template<typename T>
void read(T& w)
{
    char r;
    for(r=getchar();r<48||r>57;r=getchar());
    for(w=0;r>=48&&r<=57;r=getchar())w=w*10+r-48;
}
template<typename T>
inline void write( T w)
{
    if(w<0)
    {
        putchar('-');
        w=-w;
    }
    if(w>9)
        write(w/10);
    putchar(char(w%10+48));

}
template<typename T>
void Swap(T& a,T& b){T t=a;a=b;b=t;}
const int maxn=500003;
const int maxm=500003;
int n,m,s;
struct EDGE
{
    int to,nxt;
}edge[maxm<<1];
int ek=0;
struct node
{
    int edge1,d,f;
}tree[maxn];
inline void addEdge(int from,int too)
{
    ++ek;
    edge[ek].to=too;
    edge[ek].nxt=tree[from].edge1;
    tree[from].edge1=ek;
}
const int max2=20;
int up[maxn][max2+1];
void dfs(int k)
{
    #define now tree[k]
    for(int i=now.edge1;i;i=edge[i].nxt)
    {
        int v=edge[i].to;
        #define son tree[v]
        if(son.d==0)
        {
            son.d=now.d+1;
            son.f=k;
            dfs(v);
        }
        #undef son
    }
    #undef now
}
void initLCA()
{
    for(int i=1;i<=n;++i)
    {
        up[i][0]=tree[i].f;
    }
    for(int k=1;k<=max2&&((1<<k)<=n);++k)
    {
        for(int i=1;i<=n;++i)
        {
            up[i][k]=up[up[i][k-1]][k-1];
        }
    }
}
int getLCA(int a,int b)
{
    #define ta tree[a]
    #define tb tree[b]
    if(ta.d<tb.d)Swap(a,b);
    for(int k=max2;k>=0;--k)
    {
        if(up[a][k])
        if(tree[up[a][k]].d>=tb.d)
            a=up[a][k];
    }
    if(a==b)return a;
    for(int k=max2;k>=0;--k)
    {
        if(up[a][k]&&up[b][k])
        if(up[a][k]!=up[b][k])
            a=up[a][k],b=up[b][k];
    }
    return ta.f;
}
void input()
{
    read(n),read(m),read(s);
    int x,y;
    for(int i=1;i<=n-1;++i)
    {
        read(x),read(y);
        addEdge(x,y);
        addEdge(y,x);
    }
}
void solve()
{
    int x,y;
    for(int i=1;i<=m;++i)
    {
        read(x),read(y);
            write(getLCA(x,y));
            putchar('\n');
    }
}
int main()
{
    input();
    tree[s].d=1;
    dfs(s);
    initLCA();
    solve();
    return 0;
}