LCA（Least Common Ancestors），即最近公共祖先，是指在有根树中，找出某两个结点u和v最近的公共祖先。 ———来自百度百科

比如在上面这幅图当中：
( LCA(A,B) ---- 表示A,B的最近公共祖先。)

LCA ( 2 , 7 ) == 1 ;
LCA ( 4 , 8 ) == 1 ;
LCA ( 6 ,10) == 1;
LCA ( 5 , 6 ) == 4 ;

相信你应该理解,LCA,是什么了吧 ， 那么怎么求LCA呢？

这里我们有两种在线的算法：

  1. 暴力
  2. 倍增

暴力虽然可以计算，但是碰到数据大的题目，肯定会被 T 到飞起。

所以一般在线计算LCA我们一般使用倍增（离线可以tarjan）。

所谓倍增，就是按2的倍数来增大，也就是跳 1,2,4,8,16,321,2,4,8,16,32 …… 不过在这我们不是按从小到大跳，而是从大向小跳，即按……32,16,8,4,2,132,16,8,4,2,1来跳，如果大的跳不过去，再把它调小。

首先我们使用链式前向星存树。

然后我们令 f[i][j] 表示 i 节点的 2^j 级祖先。

于是我们可以dfs一遍，找到每个节点的 所有 2次幂的祖先。

代码：

// h[x] 为 x节点得到深度 f[i][j]与上面一样
//
void dfs(int x,int fa){
	h[x]=h[fa]+1;	f[x][0]=fa;
	for(int i=1;(1<<i)<=h[x];i++)	f[x][i]=f[f[x][i-1]][i-1];//意思是f的2^i祖先等于f的2^(i-1)祖先的2^(i-1)祖先
	for(int i=head[x];i;i=nex[i]){
		if(to[i]!=fa)	dfs(to[i],x);
	}
}

然后就是具体求LCA了：

我们先把两个点提到同一高度，再统一开始跳。但我们在跳的时候不能直接跳到它们的LCA，因为这可能会误判，比如10和11，在跳的时候，我们可能会认为7是它们的LCA，但7只是它们的祖先，它们的LCA其实是9。所以我们要跳到它们LCA的下面一层，然后输出它们的父节点，这样就不会误判了。

做之前，我们可以预处理一下 log 的值，这样跑得更快

for(int i=1;i<=n;i++)	lg[i]=lg[i-1]+(1<<lg[i-1]==i);  //预处理出log2(i)+1

代码：

int LCA(int x,int y){
	if(h[x]<h[y])	swap(x,y);//假设x是最深的节点
	while(h[x]>h[y])	x=f[x][lg[h[x]-h[y]]-1];//让两个节点一样深
	if(x==y)	return x;
	for(int i=lg[h[x]]-1;i>=0;i--)
		if(f[x][i]!=f[y][i])//如果不一样那么肯定没有到达lca ，因为两个节点的lca 向上的节点就是一样的了
			x=f[x][i],y=f[y][i];
	return f[x][0];
}

最后总代码：

#include<bits/stdc++.h>
using namespace std;
const int N=5e5+10;
int head[N],nex[N<<1],to[N<<1],tot;
int n,m,s,f[N][30],lg[N],h[N];

void add(int a,int b){
	to[++tot]=b; nex[tot]=head[a]; head[a]=tot;
}

void dfs(int x,int fa){
	h[x]=h[fa]+1;	f[x][0]=fa;
	
	for(int i=1;(1<<i)<=h[x];i++)	f[x][i]=f[f[x][i-1]][i-1];
	for(int i=head[x];i;i=nex[i]){
		if(to[i]!=fa)	dfs(to[i],x);
	}
}

int LCA(int x,int y){
	if(h[x]<h[y])	swap(x,y);
	
	while(h[x]>h[y])	x=f[x][lg[h[x]-h[y]]-1];
	
	if(x==y)	return x;
	for(int i=lg[h[x]]-1;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;i++){
		int x,y;	scanf("%d %d",&x,&y);	add(x,y);	add(y,x);
	}
	
	dfs(s,0);
	
	for(int i=1;i<=n;i++)	lg[i]=lg[i-1]+(1<<lg[i-1]==i);
	
	while(m--){
		int a,b;	scanf("%d %d",&a,&b);
		printf("%d\n",LCA(a,b));
	}
	return 0;
}