例题引入 P1967 [NOIP2013 提高组] 货车运输

分析：本题就是询问图中两点间简单路径上最小边权，本质就是最大瓶颈路最小边权，由于有多组询问，二分+判断连通性超时了，转化为最大生成树上两点之间的简单路径上的最小边权，可以用倍增解决。

首先求最大生成树，然后在最大生成树预处理 $fa[x][i],d[x][i]$

$fa[x][i]$ :表示从 $x$ 往上走 $2^i$ 的祖先 $fa[x][i]=fa[fa[x][i-1]][i-1]$

$d[x][i]$ :表示从$x$往上走$2^i$到其祖先 $fa[x][i]$ 路径上的最小值 $d[x][i]=min(d[x][i-1],d[fa[x][i-1]][i-1])$

参考代码：点击

其实本题就是 Kruskal 重构树的模板题。

---

Kruskal 重构树

Kruskal 重构树能巧妙地求解图中从 A 点走到 B 点的所有路径中，最长的边最小值是多少，或者最短的边的最大值之类的问题。

Kruskal 算法在加边时，从小到达对边进行排序，被选中的边新产生一个节点，节点的权值就是这条边的边权，同时这个节点作为根，这两个节点的根节点就是新产生节点的左右儿子。

创建 Kruskal 重构树的核心代码：

void kruskal()
{
	sort(e+1,e+m+1,cmp);
	for(int i=1;i<=2*n;i++)f[i]=i;
	for(int i=1;i<=m;i++)
	{
		int x=find(e[i].x);
		int y=find(e[i].y);
		if(x!=y)
		{
			++num;
			f[x]=f[y]=f[num]=num;
			val[num]=e[i].z;
			add(num,x);
			add(num,y);			
		}
	}
}

Kruskal 重构树的本质就是把最小生成树上的边权改成了点权，原图的节点会增加 $n-1$ 个,有性质如下：

• 原图中两个点之间的所有简单路径上最大边权的最小值 = 最小生成树上两个点之间的简单路径上的最大值 = Kruskal 重构树上两点之间的 LCA 的权值。

• kruskal 重构树是一颗二叉树，并符合二叉堆的性质。

• 重构树中代表原树中的点的节点全是叶子节点，其余节点都代表了一条边的边权。

U92652 【模板】kruskal重构树

参考代码：点击

P4768 [NOI2018]归程

分析：首先利用 dijkstra 求从 $1$ 点到其他点的最短距离，其他点 $v$ 到 $1$ 号点的最短距离，其他点 $v$ 能够坐车的情况下到达一些点，转化为：这些点到 $1$ 号点的最近距离。

然后再按照海拔高度从大到小创建 Kruskal 重构树，由于 Kruskal 重构树性质根节点海拔高度最小，也就是整个子树中海拔最低的边权，那么从某个点出发，往上走直到走到海拔高度小于等于限制的节点，以这个节点为根的子树中，点 $v$ 都可以坐车到达，这个子树叶子节点距离起点的最短距离就是答案，可以倍增维护。

参考代码：点击

P4197 Peaks

题意：给定 $n$ 个点 $m$ 条边，每个点有点权（海拔高度），每条边有边权（道路困难程度）。$q$ 组询问，从一个点 $v$ 出发，走边权不超过 $x$ 的第 $k$ 高山峰的高度。

分析：以边权从小到大创建 Kruskal 树，在重构树上从一个点出发，如果朝下走内部点权（原边）变小，也就是都能走，往上走点权变大，当遇到最后一个不超过 $x$ 的点，这个点以下的子树都是从 $v$ 出发能够到达的点。

问题就转变了，在这颗子树内寻找叶子节点第 $k$ 大的问题了。

可以利用 $dfs$ 序，将子树转变为区间，就成了区间第 $k$ 大，可以利用“可持久化线段树”解决。当然要注意Kruskal 树内部节点并不真实存在，内部点对应的是边，遇到内部点直接复制前一个线段树就好。

参考代码：点击

P4899 [IOI2018] werewolf 狼人

---

学习完毕

{{ select(1) }}

• YES
• NO