kruskal 重构树
注：默认您学会了求最小生成树的 kruskal 算法，并且知道何为最小瓶颈生成树和最小瓶颈路。
定义：
在跑 kruskal 的过程中我们会从小到大加入若干条边，我们仍然按照这个顺序加边，并且视这条边为一个节点，点权为加入边的边权。
一次加边会合并两个集合，我们分别以这两个集合的根节点为新建点的左、右儿子，然后将两个集合和新点合并为一个集合，将新建点设为根。
在进行 \(n - 1\) 轮加边后，我们就得到了一棵恰有 \(n\) 个叶子的二叉树，同时每个非叶子节点恰有两个儿子。这棵树就是 kruskal 重构树。
举个例子，这张图：
建出 kruskal 重构树是：
点上括号里的数表示点权。
实现：
其实和 kruskal 求最小生成树的实现一样，对所有边排序，依次考虑这条边可不可以被加入，通过并查集维护两点之间的联通性，没了。
struct Union_Set{
int fa[MAXN];
void init(int n){
for(register int i = 1; i <= n; i++) fa[i] = i;
}
int Find(int x){
return x == fa[x] ? x : fa[x] = Find(fa[x]);
}
}U; //并查集
void Kruskal(){
U.init(n << 1); //初始化并查集
int tot = 0; sum = n; //tot 是加进去了多少边，sum 是重构树上点的数量
sort(line + 1, line + 1 + m, cmp);
for(register int i = 1; i <= m; i++){
int u = line[i].from, v = line[i].to;
int fa_u = U.Find(u), fa_v = U.Find(v);
if(fa_u != fa_v){
++tot;
val[++sum] = line[i].dis;
Add(sum, fa_u), Add(fa_u, sum);
Add(sum, fa_v), Add(fa_v, sum);
}
if(tot == n - 1) break; //加进 n - 1 条边一定能构成树
}
}
性质：
由于 kruskal 重构树是一棵二叉树，并且是依次加边，所以它有一些美妙的性质：
如果我们将叶子节点的权值视为 \(0\)，则整棵树满足堆结构。所以任意两点间路径的最小权值的最大值即为它们 \(LCA\) 的点权。
也就是说，到点 \(u\) 的简单路径上最大边权的最小值 \(≤ val\) 的所有点 \(y\) 均在 kruskal 重构树上的某一颗子树内，且恰为这棵子树中的叶子结点。
题：
P4768 [NOI2018] 归程
\(\textit{Description}\)
\(N\) 个节点 \(M\) 条边的无向图，用 \(l\)，\(a\) 表示长度，海拔。
有 \(Q\) 次询问，给定起点 \(v\)，水位线 \(p\)，只能经过海拔不低于 \(p\) 的边，求能到达的点中距离 \(1\) 号节点最近的距离。
\(\textit{Solution}\)
首先跑一遍单源最短路，预处理出每个点到 \(1\) 号节点的最短路径，注意到这是归程，所以 spfa 会被卡，所以要用 dijstra。然后建出关于海拔 \(a\) 的 kruskal 重构树，要关于海拔 \(a\) 降序排序使得 kruskal 重构树满足大根堆性质，那么能到达的点是重构树中一个子树的所有叶子节点。然后我们去找节点 \(v\) 到根的路径上最浅的海拔不低于 \(p\) 的点，这一步可以倍增处理。然后以该节点为根的子树中的叶子结点到 \(1\) 节点的最短路径就是答案，直接 dfs 时预处理就行，不要像写这篇博的傻逼一样把树拍扁了再在 dfs 序上线段树处理最小值。
\(\textit{Code}\)
今天情况特殊，只能口胡了。
P1967 [NOIP2013] 货车运输
\(\textit{Description}\)
给定一个 \(N\) 个点 \(M\) 条边的无向图，每条边有一个权值，\(Q\) 次询问，求 \(u\)，\(v\) 两点路径上最大的权值的最小值。
\(\textit{Solution}\)
权值的限制可以想到 kruskal 重构树，求最大权值的最小值显然要按照最大生成树建重构树，\(LCA(u, v)\) 的权值即为 \(u\) 到 \(v\) 路径上的最大权值的最小值。
\(\textit{Code}\)
纯口胡，没写过，写的两个 \(\log\) 的树剖。
P3280 [SCOI2013] 摩托车交易
\(\textit{Description}\)
写了就没意思了。
\(\textit{Solution}\)
先说结论：题目里两个限制都是假的。
对于要求最后要卖光：
我们只需要尽可能多的携带黄金，不用在意是否能卖光。因为实际情况下我们可以调整购入黄金的量来达到要求。
对于不能丢弃：
我们能买黄金就尽量买，在路途中丢弃黄金和购入时购入恰好的量是等效的。
一个城市有车站的话就向上一个车站连一条边权为 \(inf\) 的边，反正最后能缀在一起就行了。
然后按照最大生成树建重构树，求两点之间的 \(LCA\)，用个变量记录一下当前携带的黄金数量模拟就行了。
\(\textit{Code}\)
纯口胡，没写过，写的两个 \(\log\) 的树剖。
P4197 Peaks
\(\textit{Description}\)
给定一个无向图，有 \(Q\) 个询问，求从点 \(v\) 出发，只经过权值小于等于 \(x\) 的边能到达的所有点中第 \(k\) 大的权值。
\(\textit{Solution}\)
kruskal 重构树和主席树缝起来。
按照最小生成树建出重构树，倍增找到点 \(v\) 的祖先中最浅的权值小于等于 \(x\) 的点 \(u\)，能到达的所有点就是以 \(u\) 为根的子树的叶子节点。
我们可以通过树剖等知识知道，一棵子树内的所有点的 dfs 序是一个连续的区间。把重构树拍扁，注意只有叶子结点存的是原图的点权，所以每个非叶子结点只需要记录它包含的叶子节点的区间就行了，然后建主席树，查询区间第 \(k\) 大即可。
\(\textit{Code}\)
今天情况特殊，只能口胡了。
P7834 [ONTAK2010] Peaks 加强版
只加强了一个强制在线，然而 kruskal 重构树就是在线做法。
[AGC002D] Stamp Rally
\(\textit{Description}\)
给定一张无向图，每次询问从 \(x\) 和 \(y\) 分别出发，一共要经过 \(z\) 个点（经过相同的点只算一次），使得走过编号最大的边最小。
\(\textit{Solution}\)
以边的编号为权值，按照最小生成树建重构树，每次二分需要走过的最大的编号，让 \(x\)，\(y\) 分别跳到最浅的满足要求的祖先。则以该节点为根的子树中的叶子结点都是可以到达的，判断两节点包含的叶子结点的数量是否大于等于 \(z\) 即可。
\(\textit{Code}\)
今天情况特殊，只能口胡了。
P3684 [CERC2016]机棚障碍 Hangar Hurdles
\(\textit{Description}\)
太长，不想写了。
\(\textit{Soltion}\)
对于每个位置求出它能通过的最大的矩形大小，转化成求最大瓶颈路问题。
求最大矩形大小可以二分查找。记录一个二维前缀和 \(sum_{i,j}\)，遇到障碍物加 \(1\)，设当前点为 \((x, y)\)，二分 \(len\)，使得\(sum_{x - len, y - len}\) 到 \(sum_{x + len, y + len}\) 的和为 \(0\)，最后最大的矩形就是 \(len \times 2 + 1\)。
然后去连边，边权是两端点能通过的最大的矩形的最小值。从当前点分别向它的右边和下边连边即可。注意的是障碍物也需要连边，否则一些不能通达的点不会出现在重构树里，查询时会寄掉。有障碍物只需要把边权设为 \(0\) 即可。
按照最大生成树去建重构树，询问就是求两点之间的 \(LCA\)，如果 \(LCA\) 的权值是 \(0\) 的话说明不能通达，判掉即可。
\(\textit{Code}\)
今天情况特殊，只能口胡了。
还有CF上的两道题，但我找不到了，咕了。
标签：重构,kruskal,叶子,权值,textit,习题,节点 From： https://www.cnblogs.com/TSTYFST/p/16889695.html