最近公共祖先LCA(lowest common ancestor)

在图论和计算机科学中，最近公共祖先（英语：lowest common ancestor）是指在一个树或者有向无环图中同时拥有v和w作为后代的最深的节点。在这里，我们定义一个节点也是其自己的后代，因此如果v是w的后代，那么w就是v和w的最近公共祖先。

最近公共祖先是两个节点所有公共祖先中离根节点最远的，计算最近公共祖先和根节点的长度往往是有用的。比如为了计算树中两个节点v和w之间的距离，可以使用以下方法：分别计算由v到根节点和w到根节点的距离，两者之和减去最近公共祖先到根节点的距离的两倍即可得到v到w的距离。
(取自维基百科对最近公共祖先的定义)

例如：

节点(x,y)的公共祖先是上面绿色的三个节点，但是最近的(即深度最深的)节点是深绿色的那个。

那么给定一个树，和树上任意两点怎么求他们的lca(u,v)呢？

朴素做法：维护一个深度数组:记录每个节点的深度，和一个父亲节点数组：方便往上面跳去找父亲。
思路：dfs预处理两个数组，然后比较a，b节点深度，深度相同，比较值，值相同直接返回(这个节点就是他们的lca),如果值不同,同时往上面跳一格(这里可以优化，就会引出倍增lca),直至相遇，如果深度不同，深度大的往上面跳，直至深度相同再用上面的步骤即可。
朴素做法思路比较简单，代码也比较好写，但是当树退化成一条链的时候这个复杂度是很大的，容易被很多题目卡掉，所以就需要倍增的思想(还没学，学完更新)。
代码:

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

const int maxn = 1e6 + 10;
struct edge{
	int v,nxt;
	edge(){}
	edge(int a,int b):v(a),nxt(b){}
}e[maxn];
int head[maxn],tot;
void add(int from,int to){
	e[++tot].v = to;
	e[tot].nxt = head[from];
	head[from] = tot;
}
int f[maxn],de[maxn];

void dfs(int fa,int s,int dep){
	f[s] = fa;
	de[s] = dep;
	for(int i = head[s]; i ;i = e[i].nxt){
		if(e[i].v != fa)
		dfs(s,e[i].v,dep + 1);
	}
}
void lca(int a,int b){
	if(a == b){
		cout<<a<<endl;return ;
	}
	if(a == 0|| b == 0)return;
	if(de[a] == de[b]){
		lca(f[a],f[b]);
	}else if(de[a] > de[b]){
		lca(f[a],b);
	}else{
		lca(a,f[b]);
	}
}
void solved(){
	int n,m,s;cin>>n>>m>>s;
	for(int i = 1; i < n; i++){
		int u,v;cin>>u>>v;
		add(u,v);add(v,u);
	}
	dfs(s,s,0);
	while(m--){
		int a,b;cin>>a>>b;
		lca(a,b);
	}
}
int main(){
	solved();
	return 0;
}

倍增算法求lca
对于朴素的算法，由于树可能是一条链，一个一个往上面跳就会很慢，于是基于这个问题，我们开发出了倍增算法，该算法需要一个函数 f ( i , j ) : 表示从节点 i 开始往树上面跳 2 ^ j次方步骤，由于2 ^ j = 2 ^ ( j - 1) + 2 ^ ( j - 1) 所以可以得到递推式 ： f [ i ][ j ] = f[ f[ i ] [ j - 1] ][ j - 1]

代码：

#include<cstdio>
#include<algorithm>
using namespace std;

const int maxn = 5e5 + 10;
int n,m,s;
struct edge{
	int v,next;
	edge(){}
	edge(int a,int b):v(a),next(b){}
}e[maxn * 2];
int dep[maxn];
int f[maxn][25];
int head[maxn],tot;
void add(int from,int to){
	e[++tot].v = to;
	e[tot].next = head[from];
	head[from] = tot;
}
void dfs(int v,int fa){
	dep[v] = dep[fa] + 1;//当前节点深度加一
	for(int i = 1; (1 << i) <= dep[v] ; i++){//在改节点的深度处能往树上跳多少步
		f[v][i] = f[f[v][i - 1]][i - 1];
	}
	for(int i = head[v]; i ; i = e[i].next){
		if(e[i].v == fa)continue;//跳过父节点，避免死循环
		f[e[i].v][0] = v;//2 ^ 0 = 1即它的父节点
		dfs(e[i].v,v);
	}
}
int lca(int x,int y){
	if(dep[x] < dep[y])swap(x,y);//为了方便处理我们采用x往上面跳
	for(int i = 20; i >= 0; i--){//2 ^ 20 理论上没问题
		if(dep[f[x][i]] >= dep[y]) x = f[x][i]; // 不断网上跳直至同一深度
		if(x == y)return x;//y本身就是x的lca
	}
	for(int i = 20; i >= 0; i--){
		if(f[x][i] != f[y][i]){//因为他们深度相同，如果大步跳可能满足不了最近。
		//所以我们找他们不相同的祖先，然后返回该节点的父节点就是lca
			x = f[x][i];
			y = f[y][i];
		}
	}
	return f[x][0];
}
void solved(){
	scanf("%d%d%d",&n,&m,&s);
	for(int i = 1; i < n; i++){
		int u,v;scanf("%d%d",&u,&v);
		add(u,v);add(v,u);
	}
	dfs(s,0);
	while(m--){
		int a,b;scanf("%d%d",&a,&b);
		printf("%d\n",lca(a,b));
	}
}
int main(){
	solved();
	return 0;
}