LCA

LCA即最近公共祖先，这里只介绍倍增这一种求法。复杂度为O((n+q)logn)。

算法基于倍增的思想。即当前节点的第2^{n祖先等于当前节点的2}(n-1)祖先的2^{(n-1)祖先。用这个思想可以在logn复杂度内处理一个节点的所有2}i祖先。且可以证明的是，处理深度更大的节点的时候，深度小的节点的信息已经处理完毕。

在预处理倍增f数组的时候，还可以做：

1. 求dfs序。
2. 求深度。
3. 丢到根距离，用于进一步求路径距离。

预处理完毕后，求lca：

1. 将两个点深度大的往上跳，直到将深度调整的一致。如果此时已经是同一个点，直接返回。
2. 将两个点一起往上跳，直到不能跳为止。
3. 返回x或y的父节点。

注意几个循环的顺序。

dfs中，倍增的那个循环必须正着跑，因为后面的值对前面的有依赖。

lca中的两个循环必须反着跑，这是二进制拆分的思想，从大到小才能唯一表示出一个数。

#include<bits/stdc++.h>
#define M 555555
using namespace std;

int n, m, s;
int x, y;
int a, b;
vector<int> g[M];
int f[M][20];
int dep[M];
int ans;

inline int read(){
   int s=0,w=1;
   char ch=getchar();
   while(ch<='0'||ch>'9'){if(ch=='-')w=-1;ch=getchar();}
   while(ch>='0'&&ch<='9') s=s*10+ch-'0',ch=getchar();
   return s*w;
}


void dfs(int u, int father) {
    dep[u] = dep[father] + 1;
    for (int i = 0; i <= 18; i++) {
        f[u][i + 1] = f[f[u][i]][i];
    }
    for (int i = 0; i < g[u].size(); i++) {
        int v = g[u][i];
        if (v == father) {
            continue;
        }
        f[v][0] = u;
        dfs(v, u);
    }
}

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

int main() {
    scanf("%d %d %d",&n,&m,&s);
    for (int i = 1; i <= n-1; i++) {
        x=read();y=read();
        g[x].push_back(y); g[y].push_back(x);
    }
    dfs(s,0);
    for (int i = 1; i <= m; i++) {
        a=read();b=read();
        ans = lca(a, b);
        printf("%d\n",ans);
    }
    return 0;
}