szzjz WiKi最小生成树
定义
定义1
给定一张带权连通图，求其边权和最小的生成树，称为最小生成树。
定义2
给定一张带权连通图，求其的生成树，称为最小生成树。
以上定义等价，证明结合kruskal的算法流程证明即可。
性质（以下性质都是充要的）
性质1
原图中任何一个环，其环上权值严格最大的边必然不在最小生成树上。
proof
假如在树上，将此边删去，则原树变成两个连通块 $T_1$、$T_2$。经过该环的另一边，可以从 $T_1$ 到 $T_2$，必然有一条边连接 $T_1$ 和 $T_2$，替换更优。这个性质是最小生成树的核心性质。
性质2
任何一条非树边对应的树上路径的最大权小于等于该非树边。
proof
由性质1反证即可。
性质3
原图中 $x$、$y$ 之间的任何一条（简单）路径的最大权，必然大于 $x$、$y$ 树上路径的最大权。
proof
原图路径每次经过非树边都可以被调整成树边路径。如果出现了非简单路径，可以将重复部分去掉（也可以不去掉）。
性质4
最小生成树最大树边边权最小。
proof
连续段dp，利用性质2，不管怎样调整都不会更优了。
求解算法
正确性都是利用性质1的充要性：任何一条边加入时，假如某个环中它是最大边，则环中其他边都已经考虑过了。
kruskal
流程：按边权从小到大考虑边能否取进生成树。
prim
流程：类似dij，本质上是实时维护了一个连通块出去的所有边，每次取最小的一条边加入生成树。 实现：有类似dij的 $O((m + n)\log m)$，也有应对完全图的 $O(n^2)$。
boruvka
流程
每次取当前连通块的最小非块内边放入边集 $E$。对 $E$ 按边权排序，当边两端点不在同一块内，就将当前边加入生成树，并合并两连通块。
得到最小非块内边的常见处理
- 直接实现：想办法跳过当前块内点，例如只考虑点与点之间的间隙点。
- 差分实现：预处理出总点集，然后每次遍历到当前连通块就先暴力减去块内的，然后求解，处理完恢复。
完全图最小生成树
形式
图的边数非常多，求最小生成树。
常见处理办法
boruvka
比较暴力的办法，容易结合DS实现，但复杂度可能多一个 $\log$。
模拟kruskal
核心是通过对kruskal流程的分析，结合性质1，从而：
- 得到一定不优的边，降低边数。
- 想办法实现kruskal的过程。
模拟prim
核心有两种考虑办法：
- 法一：考虑从当前块出发的最小的边，类似boruvka的考虑办法。
- 法二：利用新扩展的点去松弛各个没有扩展的点，类似dij的考虑办法（常见）。
传奇例题：XOR - MST
solution1: boruvka
利用预处理全局点值trie，每次差分得到块外点值trie，然后就是最大xor点对。
solution2: 模拟kruskal
trie树上刻画边权大小，假如当前考虑到前 $k$ 位都是0的边（$k$ 从大到小），那么边必然在深度为 $k$ 的节点的左右子树之间，直接连复杂度会退化。考虑每次只取从每个点出发最小的边，因为次大的一定不优。将这些边按大小排序，跑kruskal即可。复杂度 $O(n\times\log V\times\log n)$。
solution3：模拟prim
此题好像没办法用，尽力了。
瓶颈路问题（性质4的扩展）
经验性事实
当你在二分答案的check部分使用了并查集时，很有可能可以用最小生成树。
kruskal构建的特殊最小生成树
按秩合并实现的并查集恰好对应了一棵最小生成树
性质
- 树高是 $\log$ 的，可以支持各种暴力。
- 两点的瓶颈一定路径上lca的左边或右边的边。
最大的优点
写起来特别方便，常数特别小。
kruskal重构树
流程
每一条生成树上的边对应重构树上一个非叶点，叶子都是原节点。每次并查集合并时，给当前边新建一个点，赋点权为当前边权，然后儿子是合并的集合的代表，然后将当前节点作为被合并的集合的代表。
性质
- 重构树是大根堆，二叉树。
- 两点路径的瓶颈路的瓶颈是其lca点权。
- 求一个点在瓶颈 $\leq lim$ 的情况下能到的点，就是可以其满足点权 $\leq lim$ 最浅祖先对应子树中的点。
最大的优点
性质丰富。
点权多叉重构树
处理点权瓶颈路
流程
将边换成点考虑kruskal（本质上是模拟kruskal）。将点按权从小到大排序，假设当前到了 $x$，权 $w[x]$。枚举出边 $(x, y)$，只考虑 $w[x]\geq w[y]$ 的，然后将能连的连起来，同时 $x$ 是他们的父亲。
次小生成树
根据性质1，次小生成树必然是由一条非树边替换其对应路径上的最大边形成的。