XP04-02 DAY06

F,IW

2025-08-07 20:48:17

发布于：上海

5阅读

0回复

0点赞

今日主要学习树论。

一.最近公共祖先（LCA）

最近公共祖先的求解主要分为几个部分：
1.初始化：加边，初始化每个节点的祖先节点，初始化每个节点的深度。
加边：使用vector存储，注意一共输入 $n-1$ 跳条双向边。
初始化每个祖先节点：
f[x][0]表示节点 $x$ 的父亲。
f[x][1]表示节点 $x$ 的祖父（父亲的父亲）。
f[x][2]表示节点 $x$ 的超级祖父（祖父的祖父）。
由此可知： $f[x][i]=f[f[x][i-1]][i-1]$
初始化每个节点的深度：每个节点的深度=每个节点的父节点深度+1
2.求最近公共最先：将两个点提升至同一高度，找寻它们的公共祖先。
将两个点提升至同一高度：一层一层的提升会超时间复杂度，选择倍增的思想。
寻找它们的公共祖先：从后往前找，使用排除的思想。
模版：链接描述
代码：

#include<bits/stdc++.h>
using namespace std;
int n,m,s;
vector<int>v[500005];
int deep[500005];
int f[500005][30];
void dfs(int x,int pos){
	f[x][0]=pos;
	deep[x]=deep[pos]+1;
	for(int i=1;(1<<i)<=n;i++){
		f[x][i]=f[f[x][i-1]][i-1];
	}
	for(int i=0;i<v[x].size();i++){
		if(v[x][i]==pos)continue;
		dfs(v[x][i],x);
	}
}
int lca(int a,int b){
	if(deep[a]<deep[b])swap(a,b);
	int len=deep[a]-deep[b];
	for(int i=19;i>=0;i--){
		if(len>>i&1)a=f[a][i];
	}
	if(a==b)return a;
	for(int i=19;i>=0;i--){
		if(f[a][i]==f[b][i])continue;
		a=f[a][i];
		b=f[b][i];
	}
	return f[a][0];
}
int main(){
	cin>>n>>m>>s;
	for(int i=1;i<=n-1;i++){
		int x,y;
		cin>>x>>y;
		v[x].push_back(y);
		v[y].push_back(x);
	}
	dfs(s,0);
	for(int i=1;i<=m;i++){
		int a,b;
		cin>>a>>b;
		cout<<lca(a,b)<<endl;
	}
	return 0;
}

二.树上路径最小值

其实和上一题差不多。
但是需要求最小点权，所以需要多加一个 $mi[][]$ 数组。
$mi[][]$ 和上一道题目中的 $f[][]$ 差不多。
它表示的是节点 $x$ 到 $x$ 的父/祖父/超级祖父节点的最小点权。
这是 $mi[][]$ 的计算公式： $mi[i][j]=min(mi[i][j-1],mi[f[i][j-1]][j-1]);$
代码：

#include<bits/stdc++.h>
using namespace std;
int n,q;
vector<int>v[500005];
int w[500005];
int f[500005][20];
int mi[500005][20];
int deep[500005];
void dfs(int x,int pos){
	f[x][0]=pos;
	mi[x][0]=min(w[x],w[pos]);
	deep[x]=deep[pos]+1;
	for(int i=1;(1<<i)<=19;i++){
		f[x][i]=f[f[x][i-1]][i-1];
		mi[x][i]=min(mi[x][i-1],mi[f[x][i-1]][i-1]);
	}
	for(int i=0;i<v[x].size();i++){
		if(v[x][i]==pos)continue;
		dfs(v[x][i],x);
	}
}
int lca(int u,int v){
    if(u==v)return min(w[u],w[v]);
	if(deep[u]<deep[v])swap(u,v);
	int len=deep[u]-deep[v];
	int minx=INT_MAX;
	for(int i=19;i>=0;i--){
		if(len>>i&1){
			minx=min(minx,mi[u][i]);
			u=f[u][i];
		}
	}
	if(u==v)return minx;
	for(int i=19;i>=0;i--){
		if(f[u][i]==f[v][i])continue;
		minx=min(minx,min(mi[u][i],mi[v][i]));
		u=f[u][i];
		v=f[v][i];
	}
	minx=min(minx,min(mi[u][0],mi[v][0]));
	return minx;
}
int main(){
	w[0]=INT_MAX; 
	cin>>n>>q;
	for(int i=1;i<=n;i++)cin>>w[i];
	for(int i=1;i<=n-1;i++){
		int x,y;
		cin>>x>>y;
		v[x].push_back(y);
		v[y].push_back(x);
	}
	dfs(1,0);
	for(int i=1;i<=q;i++){
		int x,y;
		cin>>x>>y;
		cout<<lca(x,y)<<endl;
	}
	return 0;
}