最近公共祖先简称 LCA（Lowest Common Ancestor）。两个节点的最近公共祖先，就是这两个点的公共祖先里面，离根最远的那个。 ——OI Wiki
我们首先想到的肯定就是暴力往上爬，直到它们相遇。但是这个算法在数据量很大的时候就会超时。因此我们有了倍增优化的 LCA。
倍增是什么呢？顾名思义，就是每次翻倍跳。但是在这里，我们不是从小到大跳，而是从大到小跳。
那么这个算法怎么实现呢？我们先保存每个节点的深度和祖先节点。其中 fath[x][i] 表示节点 \(x\) 的第 \(2^i\) 个祖先，可以用 dfs 预处理出来，from[x] 表示节点 \(x\) 的父节点，depth[x] 表示节点 \(x\) 的深度。
现在我们就我们可以开始求 LCA 了。第一步，我们要将 \(u,v\) 两点跳转到同一深度。计算出 \(u,v\) 的深度之差 \(y\)，对 \(y\) 进行二进制的拆分，也就是将 \(y\) 次跳转优化为 \(y\) 的二进制中所含的 \(1\) 的个数次跳转。如果两点相遇则问题解决。第二步，我们从可能的最大步数开始一直进行尝试，不断减半，如果跳到的地方相同就不跳，否则就跳，再一步一步往上调整，直到找到最近公共祖先。
#include<iostream>
#include<algorithm>
#include<cmath>
#include<cstring>
#include<vector>
using namespace std;
const int N=5e5+5;
int fath[N][20],from[N],depth[N],n,m,c,k,x,y,q,u,v,t,ans,root=0;
vector<int> G[N];
void getDepth_dfs(int root){
for(unsigned i=0;i<G[root].size();i++){
int next=G[root][i];
depth[next]=depth[root]+1;
getDepth_dfs(next);
}
}
void getParents(){
for(int up=1;(1<<up)<=n;up++)
for(int i=1;i<=n;i++)
fath[i][up]=fath[fath[i][up-1]][up-1];
}
int LCA(int u,int v){
if(depth[u]<depth[v])
swap(u,v);
int i=-1;
while((1<<(i+1))<=depth[u])
i++;
for(int j=i;j>=0;j--)
if(depth[u]-(1<<j)>=depth[v])
u=fath[u][j];
if(u==v) return u;
for(int j=i;j>=0;j--) {
if(fath[u][j]!=fath[v][j]) {
u=fath[u][j];
v=fath[v][j];
}
}
return fath[u][0];
}
int main(){
ios::sync_with_stdio(false);
memset(fath,-1,sizeof(fath));
memset(from,-1,sizeof(from));
memset(depth,-1,sizeof(depth));
cin>>n>>m;
for(int i=1;i<=n-1;i++){
cin>>x>>y;
G[x].push_back(y);
fath[y][0]=x;
from[y]=x;
}
depth[root]=1;
getDepth_dfs(root);
getParents();
while(m--){
cin>>x>>y;
ans=LCA(x,y);
cout<<ans<<endl;
}
return 0;
}