LCA (Least Common Ancestors)，即为最近公共祖先，求LCA也是求树上两点最短路的重要一环。

朴素算法求LCA

首先将深度较大的节点沿着父亲向上跳转，与另一点深度相同后同时跳转，直至跳到同一父亲

1
2
3
4
5
6
7
8
9
10
11
12
13
int lca(int u, int v) {
    if (depth[u] < depth[v]) {
        swap(u, v);
    }
    while (depth[u] > depth[v]) {
        u = parent[u];
    }
    while (u != v) {
        u = parent[u];
        v = parent[v];
    }
    return u;
}

倍增法求LCA

思路大致与朴素算法相同，但跳转时不是一次跳一个父亲，而是跳$2^k$个父亲，跳深度较大的节点时$k$为最大的满足$2^k \leq depth[u]-depth[v]$的数。而共同跳转时，$k$从大到小枚举，直至跳到同一父亲。有点像在树上维护了一个ST表。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
void initLOG2(int n){
	for(int i=1;i<=n;++i){
		LOG2[i]=LOG2[i-1]+(1<<LOG2[i-1]==i);
	}
}

void dfs(int x,int fath){//预处理fa数组,fa[x][i]表示x的第2^i个祖先
	fa[x][0]=fath,de[x]=de[fath]+1;
	
	for(int i=1;i<=LOG2[de[x]];++i)
		fa[x][i]=fa[fa[x][i-1]][i-1];//x的第2^i个祖先=第2^(i-1)个祖先的第2^(i-1)个祖先
	
	for(int i=0;i<g[x].size();++i){
		if(g[x][i]!=fath)dfs(g[x][i],x);
	}
}

int LCA(int a,int b){
	
	if(de[a]>de[b])swap(a,b);
	int r=de[b]-de[a];
	while(de[b]>de[a]){
		r=de[b]-de[a];
		b=fa[b][LOG2[r]-1];
	}
	if(a==b)return a;//如果a,b此时相等直接返回a
	for(int i=LOG2[de[a]]-1;i>=0;--i)//从大到小枚举
		if(fa[a][i]!=fa[b][i])
			a=fa[a][i],b=fa[b][i];
	return fa[a][0];//循环出来时a,b的父亲就是LCA
}