对于一棵树里的任意两个节点，若他们的深度相同，显然他们到最近公共祖先的距离是相同的，我

们可以利用这个性质来求最近公共祖先。

　　对于两个深度相同的节点，若此时父亲节点是同一个点，那么最近公共祖先就是父亲节点，如果不

是的话我们就让他们向上跳到自己的父亲节点，再判断他们的父亲节点是否相同，重复该操作直到父亲节

点相同时结束。

　　例如3和6，他们的父亲节点都为 2，因此直接返回最近公共祖先为 2，而 6 和 7 由于父亲节点分别为

2 和 4 不相同，因此我们让他们向上跳到 2 和 4 ，而 2 和 4 的父亲节点都为 1，此时我们就可得出 6 和 7

的最近公共祖先是 1。

　　方法很好实现，但时间效率令人堪忧。像这样一步一步向上跳，就成了一条链，时间效率也就为n，

显然太低。

　　我们可以运用倍增的思想。

　　对于相同深度的 u , v 两点，我们观察他们向上 2 ^j  辈的祖先节点（2 ^j 大于等于树的最大深度），此

时若祖先节点相同（超出树的深度我们默认都为0），我们将 j--，因为此时我们并不知道该祖先节点是否

为最近公共祖先。若祖先节点不同，说明最近公共祖先还在其之上，因此我们向上跳到祖先节点处。

　　跳到祖先节点后我们是否需要将 j 重置呢？我们来想一下，假设向上 2 ^j 的祖先节点相同，而2 ^j-1 的

祖先节点不同，此时 u 和 v 跳到 2 ^j-1 的祖先节点处，此时若再跳 2 ^j-1 次，不就回到了原来 u , v 的2 ^j 的

祖先节点处了吗？再往上的祖先节点一定也是相同的。因此我们不用再将 j 重置，因为再往上走相同甚至

更多辈的祖先一定是相同的，所以直接继续 j--即可。

　　一直到 j 为0后，此时 u 和 v 的位置一定在最近公共祖先的儿子节点。（类似于二进制拆分，从大到

小对 j 进行遍历时，如果 2 ^j 小于此时到最近公共祖先的距离，就加上 2 ^j 即向上跳，加完之后就为到最近

公共祖先的儿子节点的距离）

　　可以结合下图理解一下。

　　具体代码实现如下。

 1 int f[maxn][30];// f[i][j]表示i点向上跳2的j次方的祖先节点（f[i][0]就为父亲节点）
 2 int Lca(int u,int v){
 3     if(u==v) return u;
 4     for(int i=20;i>=0;i--){
 5         if(f[u][i]!=f[v][i]){//祖先相同不一定是最近公共祖先，若祖先不同则往上跳 （因为最近公共祖先一定还在上面） 
 6             u=f[u][i],v=f[v][i];
 7         }
 8     }//跳完最后一定在最近公共祖先的儿子节点上 
 9     return f[u][0];//随便返回一个 
10 }

　　看到这个 f 数组一定想到了ST表，那么我们还要对其进行预处理。我们可以利用类似的思路进行处

理。

　　由于 2 ^j  = 2 ^j-1 + 2 ^j-1 ，因此对于 i 点向上 2 ^j  辈的祖先节点，实际上就等同于 i 点向上 2 ^j-1 辈的祖

先再向上跳 2 ^j-1 次。所以我们就得到了对ST表预处理的公式：f [ i ] [ j ] =f [ f [ i ] [ j - 1 ] ] [ j - 1 ] 。

    for(int i=1;i<=20;i++){//预处理u节点的祖先们 
        int x=f[u][i-1];
        f[u][i]=f[x][i-1];//u的(2的i次方)祖先相当于是u的（2的i-1次方）祖先向上跳（2的i-1次方）次 
    }

　　注意提前标记 u 节点的父亲节点！

　　对于相同深度的任意两点这样就能结束了，那么深度如果不同呢？

　　显然我们可以将深度大的点向上跳一直跳到和另一个点一样深。

　　我们使得 u 深度始终大于 v，用一个 len 来记录 u v 的深度之差，也就是说 u 需要向上跳 len 次。

　　这里我们可以使用二进制拆分将len拆分，然后再跳对应的步数即可。

　　举个栗子

　　例如这个图中的 3 和 8 ，显然我们需要将 8 向上跳到与3深度相同的地方，需要向上跳 5 步。而 5 二

进制拆分可以分为 4 和 1 ，因此我们先向上跳1次也就是跳到 f [ 8 ] [ 0 ] = 1处，再向上跳4步也就是f [ 1 ][

2 ]= 2处就可以了。

　　代码实现：

int d[maxn];//记录深度 
int f[maxn][30];// f[i][j]表示i点向上跳2的j次方的祖先节点（f[i][0]就为父亲节点） 
int Query(int u,int v){
    if(d[u]<d[v]) swap(u,v);//保证u的深度大于等于v
    int len=d[u]-d[v];//len为深度差，u总共需要向上跳len次
    for(int i=0;i<=20;i++){
        if(1<<i&len){//相当于二进制拆分（2的i次方每次只有一位为1,len写成二进制后对应数位为一结果位才为一，对应数位之和恰好为len）
        //例如len=10，二进制为1010，i为0时(1<<i)=1；1010&1=0；i为1时1010&10=10！=0；i为3时1010&1000=1000；1000+10=1010=len; 
            u=f[u][i];//u向上跳（1<<i）次 
        }
    }//跳完此时u,v深度一样 
    return Lca(u,v);
}

　　这样我们就可以写出完整的代码了。

#include<cstdio>
#include<iostream>
#include<cmath>
using namespace std;
const int maxn=5e5+5;
struct Edge{
    int to,next;
}e[maxn*2];
int len,head[maxn];
void Insert(int u,int v){
    e[++len].to=v;
    e[len].next=head[u];
    head[u]=len;
}
int n,q,s;
int f[maxn][30];// f[i][j]表示i点向上跳2的j次方的祖先节点（f[i][0]就为父亲节点） 
void Read(){
    scanf("%d%d%d",&n,&q,&s);
    for(int i=1;i<n;i++){
        int u,v;
        scanf("%d%d",&u,&v);
        Insert(u,v);
        Insert(v,u);
    }
}
int d[maxn];//记录深度 
bool vis[maxn]; 
void dfs(int u,int fa,int deep){//dfs遍历整个树 (fa为父节点，deep为深度)
    vis[u]=1;
    f[u][0]=fa,d[u]=deep;
    for(int i=1;i<=20;i++){//预处理u节点的祖先们 
        int x=f[u][i-1];
        f[u][i]=f[x][i-1];//u的(2的i次方)祖先相当于是u的（2的i-1次方）祖先向上跳（2的i-1次方）次 
    }
    for(int i=head[u];i;i=e[i].next){
        int v=e[i].to;
        if(!vis[v]){
            dfs(v,u,deep+1);
        }
    } 
}
int Lca(int u,int v){
    if(u==v) return u;
    for(int i=20;i>=0;i--){
        if(f[u][i]!=f[v][i]){//祖先相同不一定是最近公共祖先，若祖先不同则往上跳 （因为最近公共祖先一定还在上面） 
            u=f[u][i],v=f[v][i];
        }
    }//跳完最后一定在最近公共祖先的儿子节点上 
    return f[u][0];//随便返回一个 
}
int Query(int u,int v){
    if(d[u]<d[v]) swap(u,v);//保证u的深度大于等于v
    int len=d[u]-d[v];//len为深度差，u总共需要向上跳len次
    for(int i=0;i<=20;i++){
        if(1<<i&len){//相当于二进制拆分（2的i次方每次只有一位为1,len写成二进制后对应数位为一结果位才为一，对应数位之和恰好为len）
        //例如len=10，二进制为1010，i为0时(1<<i)=1；1010&1=0；i为1时1010&10=10！=0；i为3时1010&1000=1000；1000+10=1010=len; 
            u=f[u][i];//u向上跳（1<<i）次 
        }
    }//跳完此时u,v深度一样 
    return Lca(u,v);
}
void sol(){
    Read();
    dfs(s,0,1);
    int ans[maxn];
    for(int i=1;i<=q;i++){
        int u,v;
        scanf("%d%d",&u,&v);
        ans[i]=Query(u,v);
    }
    for(int i=1;i<=q;i++){
        printf("%d\n",ans[i]);
    }
} 
int main(){
    sol();
    return 0;
}