最近公共祖先LCA（倍增思想）

void dfs(int rt,int fr){//rt-当前节点 fr-rt的父结点
	//搜索，遍历树的结点，并记录深度信息
    //dep[x] 结点x的深度 fa[x] 结点x的父结点
	for(int i=0;i<(int)G[rt].size();i++){
		int u=G[rt][i];
		if(u==fr) continue;//如果 遍历到rt的父结点，则跳过
		dep[u]=dep[rt]+1;
        fa[u]=rt;//更新 rt为 u 的父结点
		dfs(u,rt);
	}
}

int query_LCA(int x,int y){
	
	if(dep[x]<dep[y]) swap(x,y); //保证dep[x]>=dep[y]
	
	//1. 提到同一深度  将x往上提
	while(dep[x]!=dep[y]){
		x=fa[x];//往上提
	}
	//2. 同时往上提，直到重复
	while(x!=y){
		x=fa[x];
		y=fa[y];
	}
	return x;
}

for(int j=1;j<=Log[n];j++){
    for(int i=1;i<=n;i++){
        fa[i][j]=fa[fa[i][j-1]][j-1];
    }
}

int dev=dep[x]-dep[y];
while(dev){
    int k=lowBit(dev);
    x=fa[x][Log[k]];
    dev&=(dev-1);
}	

for(int i=Log[dep[x]];i>=0;i--){
    if(fa[x][i]!=fa[y][i]){
        x=fa[x][i];
        y=fa[y][i];
    }
}
return fa[x][0];

#include <iostream>
#include <cstdio>
#include <vector>
#include <cstring>
using namespace std;
const int N=5e5+5;
vector<int>G[N];
int n,m,s;
int dep[N];
int fa[N][20];//fa[x][k] x的2^k 辈父亲结点
int Log[N];

void dfs(int rt,int ff){
	//搜索，遍历树的结点并，并记录深度信息
	for(int i=0;i<(int)G[rt].size();i++){
		int u=G[rt][i];
		if(u==ff) continue;//如果 遍历到rt的父结点，则跳过
		dep[u]=dep[rt]+1;
		fa[u][0]=rt;//更新 rt为 u 的父结点
		dfs(u,rt);
	}
}

int lowBit(int x){
	return x&(-x);
}

int query_LCA(int x,int y){
	if(dep[x]<dep[y]) swap(x,y); //保证dep[x]>=dep[y]
	//1. 提到同一深度  将x往上提
	if(dep[x]!=dep[y]){//不同深度，则将x向上提至相同深度
		int hx=dep[x]-dep[y];
		while(hx){
			int k=lowBit(hx);
			x=fa[x][Log[k]];
			hx&=(hx-1);
		}	
	}
	
	if(x==y) return x;
	//2. 同时往上提，直到重复		
	for(int i=Log[dep[x]];i>=0;i--){
		if(fa[x][i]!=fa[y][i]){
			x=fa[x][i];
			y=fa[y][i];
		}
	}
	return fa[x][0];
}


int main(){
	int x,y,a,b;
	scanf("%d%d%d",&n,&m,&s);
	for(int i=1;i<n;i++){
		scanf("%d%d",&x,&y);
		G[x].push_back(y);
		G[y].push_back(x);
	}
	
	dep[s]=1;
	dfs(s,0);
	
	//预处理Log[]数组 ， Log[x]=log2(x)
	for(int i=2;i<=n;i++){
		Log[i]=Log[i/2]+1;
	}
	
	//	//预处理fa[x][y]= x的第2^y辈的结点
	for(int j=1;j<=Log[n];j++){
		for(int i=1;i<=n;i++){
			fa[i][j]=fa[fa[i][j-1]][j-1];
		}
	}	
	
	for(int i=1;i<=m;i++){
		scanf("%d%d",&a,&b);
		printf("%d\n",query_LCA(a,b));
	}
	return 0;
}