题解：P3379 【模板】最近公共祖先（LCA）

题目描述

给定一棵包含

n

个节点的树，处理

m

次查询，每次查询两个节点的最近公共祖先。

算法思路

‌1. 预处理‌：通过DFS初始化每个节点的深度和直接父节点。

2. 倍增

核心思想：每个节点的

2^j

级祖先可以通过两次

2^{j-1}

级跳跃得到。

即：

f[i][j]=

节点i向上跳

2^{j-1}

步后的祖先，再向上跳

2^{j-1}

步。

$f[i][j]$ 表示第 $i$ 个节点向上跳 $2^j$ 步所到达的节点位置。

可以易知

f[i][0]

是节点

i

的父亲节点。

由此可得出递推式：

$f[i][j]=f[f[i][j-1]][j-1]$

代码如下：

CPP

for(int j=1;(1<<j)<=n;j++){
	for(int i=1;i<=n;i++){
		f[i][j]=f[f[i][j-1]][j-1];
	}
}

分析：

循环逻辑‌

A. 外层循环 $j$ ：

‌作用‌：枚举跳跃步长的指数

j

，即

2^j

步。 ‌终止条件‌：

2^j\leq n

。

因为树的高度最多为

n

，超过

2^j>n

的跳跃无意义。

B. 内层循环 $i‌$ ：

‌作用‌：对每个节点

i

，计算其

2^j

级祖先。

3. 查询LCA‌：将两个节点调整到同一深度，然后同时向上跳跃，找到最近的公共祖先。

代码实现

CPP

#include<bits/stdc++.h>
#define int long long
using namespace std;
const int N=1e6+7;
int n,m,s,f[N][30],dep[N];
bool vis[N];
vector<int> g[N];
void dfs(int u,int fa){
	f[u][0]=fa;//f[u][0]表示第u个节点的父亲节点
	dep[u]=dep[fa]+1;//每个节点的深度是其父亲节点的深度+1
	for(auto v:g[u]){
		if(v==fa)continue;//防止遍历回父亲节点
		dfs(v,u);
	}
}
int lca(int u,int v){
	if(dep[u]<dep[v])swap(u,v);//令u始终在v的下方
	for(int i=22;i>=0;i--){
		if(dep[f[u][i]]>=dep[v])u=f[u][i];
		//将u往上拉，直至dep[u]=dep[v] 
	}
	if(u==v)return u;//此时v为u的祖先，直接返回u
	//此时u与v已在同一深度上
	for(int i=22;i>=0;i--){
		if(f[u][i]!=f[v][i]){
			u=f[u][i];
			v=f[v][i];
			//将u和v一同向上拉，直至两点位于同一个节点上
		}
	}
	return f[u][0];//或f[v][0](u与v共同的父亲节点) 
}
void init(){
	//倍增初始化
	for(int j=1;(1<<j)<=n;j++){
		for(int i=1;i<=n;i++){
			f[i][j]=f[f[i][j-1]][j-1];
		}
	}
}
signed main(){
	ios::sync_with_stdio(false);
	cin.tie(0),cout.tie(0);
	cin>>n>>m>>s;
	for(int i=1;i<n;i++){
		int u,v;
		cin>>u>>v;
		g[u].push_back(v);
		g[v].push_back(u);
		//存入数据
	}
	dfs(s,0);
	init();
	for(int i=1;i<=m;i++){
		int u,v;
		cin>>u>>v;
		cout<<lca(u,v)<<"\n";
	}
	return 0;
}

~~蒟蒻第一次写题解，可能很垃~~

题解：P3379 【模板】最近公共祖先（LCA）

文章操作

题目描述

算法思路

$f[i][j]$ 表示第 $i$ 个节点向上跳 $2^j$ 步所到达的节点位置。

由此可得出递推式：

$f[i][j]=f[f[i][j-1]][j-1]$

分析：

循环逻辑‌

A. 外层循环 $j$ ：

B. 内层循环 $i‌$ ：

代码实现

相关推荐

评论

题解：P3379 【模板】最近公共祖先（LCA）

文章操作

题目描述

算法思路

f[i][j]f[i][j]f[i][j]表示第iii个节点向上跳2j2^j2j步所到达的节点位置。

由此可得出递推式：

f[i][j]=f[f[i][j−1]][j−1]f[i][j]=f[f[i][j-1]][j-1]f[i][j]=f[f[i][j−1]][j−1]

分析：

循环逻辑‌

A. 外层循环jjj：

B. 内层循环i‌i‌i‌：

代码实现

相关推荐

评论

$f[i][j]$ 表示第 $i$ 个节点向上跳 $2^j$ 步所到达的节点位置。

$f[i][j]=f[f[i][j-1]][j-1]$

A. 外层循环 $j$ ：

B. 内层循环 $i‌$ ：