2023/04/LCA（倍增思想）

定义

最近公共祖先简称LCA(Lowest Common Ancestor)。两个节点的最近公共祖先指的是这两个点的公共祖先中离根最远的那个。

算法

朴素算法

首先可以求出每个节点的深度，这个过程可以使用深度优先搜索的方式进行处理。

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;
}

此时由于每次上提都是一步一步的上提，若遇见规模较大的情况，或“斜树”形态的数，会超时，复杂度为$O(N)$。

倍增算法

利用倍增的思想，每次不再是一步步的上提，而是一次上提多步，从而实现快速找到最近公共祖先的目的。

设f[i][j] 为结点i的第$2^j$ 个父辈。

由此可得状态转移方程：$f[i][j]=f[f[i][j-1]][j-1]$ 。

可利用下图理解状态转移方程。

可以使用双重循环对f[i][j]进行维护。

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];
    }
}

解决加快将两个结点提到相同深度的速度。

设两结点的高度差为$dev=dep[x]-dep[y]$

将$dev$看做二进制形式可被表达为 $2^{x_1} + 2^{x_2}+\cdots + 2^{x_k}$ 。$x_i$ 代表$dev$二进制中为1的位数。那么我的x结点要提高y的高度只需要进过$k$(dev二进制的1的个数)步就可以。

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

当x、y高度相同后，再把两者同时往上提，直到父辈重复相同为止。

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;
}