Lca的四种写法(3) 转rmq问题

#LCA专题之转RMQ

LCA(Lowest Common Ancestors)即最近公共祖先。在图论中，我们往往需要解决一些树上的操作，而很多时候我们需要求出某两个结点的最近公共祖先

怎么将LCA 问题转化成RMQ问题呢，所谓RMQ就是 (Range Minimum/Maximum Query)，这里我们会转化成求区间最小值的算法。 具体做法是，我们对整颗树进行dfs,记录每个点的第一次访问顺序id[u] = tsp,每次访问的是哪个点，每次回溯到根节点我们都认为他访问了一遍根节点，vis[tsp] tsp(timestamp 时间戳)我们用来记录访问了几个点，dep[tsp]每次访问的点的深度。

假设一棵树是 8 1 2 1 3 2 4 2 5 3 6 5 7 5 8

我们的访问出来的数组就是 tsp 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 vis 1 3 6 3 1 2 5 8 5 7 5 2 4 2 1
dep 0 1 2 1 0 1 2 3 2 3 2 1 2 1 0

这样我们假设询问是7 和 8，id[7] = 10,id[8] = 8,dep[8]到dep[10]中最小的dep的下标记为flag = 9，lca就是vis[9] = 5

具体实现如下： 邻接表存边

struct Edges{
	int s,t,nxt;
	Edges(){
		s = t = nxt = 0;
	}
	Edges(int _s,int _t,int _nxt):s(_s),t(_t),nxt(_nxt){}
}e[M*2];
int tot = 1,head[N]；
inline void add(int s,int t){
	e[++tot] = Edges(s,t,head[s]);
	head[s] = tot;
	e[++tot] = Edges(t,s,head[t]);
	head[t] = tot;
}

dfs记录我们需要的信息

void dfs(int u,int fa,int d){
	id[u] = tsp;
	vis[tsp] = u;
	dep[tsp++] = d;
	int v;
	for(int i = head[u];i;i = e[i].nxt){
		v = e[i].t;
		if(v == fa)continue;
		dfs(v,u,d+1);
		vis[tsp] = u;
		dep[tsp++] = d;
	}	
}

倍增st表

memset(dp,0x3f,sizeof(dp));
for(int i=1;i<tsp;++i){
	dp[i][0] = dep[i];
}
for(int j=1;j<=17;++j){
	for(int i=1;i<tsp;++i){
		dp[i][j] = min(dp[i][j-1],dp[i+(1<<(j-1))][j-1]);
	}
}

我这里写的那道题只需要知道lca的深度，所以我没有求lca，但是要求lca也很简单，在倍增dp数组的时候加一个flag数组记录最小值的下标和他同步倍增就行了

int lca(int u,int v){
	u = id[u];
	v = id[v];
	if(u==v)return dep[u];
	if(u>v)swap(u,v);
	int len = log2(v-u);
	return min(dp[u][len],dp[v-(1<<len)+1][len]);
}

这样就能把LCA转成RMQ问题求解了。

有空再配图