例题引入 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重构树

参考代码：点击

Kruskal 重构树用途

Kruskal 重构树，由于按照边权排序，生成树对应点权是单调的，越往上走点权越大(或越小)。 那么在给定起点 $v$，限定边权不能超过 lim 的情况下，在原图中从 $v$ 出发能到达的点是一个连通块，这个连通块对应 Kruskal 重构树上一个子树，而由于有单调性，可以倍增在 $O(\log{n})$ 求出这个子树的根，问题往往就变成维护子树中信息。

P4768 [NOI2018]归程

【题意简化】给定一个 $n$ 个点 $m$ 条边的图，边权有两个：长度、海拔高度。

给定 $Q$ 组询问， 给定起点 $v$ 和水位线 $S$ 。 海拔低于 $S$ 的边将会被淹没，汽车可以开往任意没有被淹没的城市。汽车无法走的路只能步行，在这种情况下，询问从起点 $v$ 回到 $1$ 的步行最短距离，强制在线。$(n\le 2\times 10^5 , m \le 4 \times 10^5, Q \le 4 \times 10^5)$

【分析】：首先利用 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 狼人

【题意简化】给定一个 $n$ 个点 $m$ 条边的图 , $Q$ 次询问，给定 $S_i,E_i,L_i,R_i$ , 询问是否存在一条路径，满足先只走编号超过 $L_i$ 的点，再走编号不超过 $R_i$ 的点 ，如果存在输出 1 否则输出 0 。

【分析】我们发现起点能走的是一个连通块，终点出发能走的是一个连通块。启发我们建立两棵 Kruskal 重构树：一颗边权取两个点最小值，边权从大到小排序建 Kruskal 重构树，那么在重构树上，从起点出发越往上越小，直到最后一个大于等于 $Li$ 的节点(可以倍增求出)。同理，另外一颗边权取两个点最大值，按边权从小到大排序，从终点出发能到达的点，对应是一个子树。

问题就转换为：两棵子树中，是否存在重合点。 利用 $dfs$ 序 , 子树对应区间，就是询问两个区间内，是否有重合点。

问题变为，两个序列，询问第一个序列 $[l_i,r_i]$ 与第二个序列 $[L_i,R_i]$ 是否有公共点。

对于第一个序列 $a_i$ , 找到 $a_i$ 在第二个序列的位置 $p[a_i]$ , 创建可持久化线段树，在可持久化线段树 $root[r_i]$ 去掉 ($root[l_i-1]$) ，查询区间 $[L_i,R_i]$ 区间和，区间和大于 0 说明有重合点。

学习完毕

{{ select(1) }}

• YES
• NO