Boruvka 求最小生成树
Boruvka 算法的思想基于每个点的最短邻边一定在最小生成树上。算法流程是每轮对每个连通块找到一条连向另一连通块的最短边，然后合并两端点。因为每轮连通块数量至少减半，所以一共会进行 \(O(\log n)\) 轮。
相比 Kruskal 和 Prim，Boruvka 在求稠密图的最小生成树上具有优势，前提是能快速找到一个点连向与它不同连通块的最短边。
1. CF1648E Air Reform
我们先考虑如何求给定两点在原图的最短路。套路地，建出 Kruskal 重构树，最短路就是两点 \(\text{LCA}\) 的权值。
对于在补图的最短路，我们希望如法炮制，建出补图的 Kruskal 重构树。但是由于边数太多无法跑 Kruskal。不妨退一步，建出补图的最小生成树，那么两点的最短路就是这两点在最小生成树上的简单路径的最大边权。
求一个稠密图的最小生成树，可以考虑 Boruvka 算法。其思想基于每个点的最短邻边一定在最小生成树上，流程是每轮对每个连通块找到一条连向另一连通块的最短边，然后合并两端点。因为每轮连通块数量至少减半，所以一共会进行 \(O(\log n)\) 轮。
于是现在我们考虑对每个点 \(u\)，求出它连出去的最小出边，并且边的另一端点不和 \(u\) 在同一连通块。我们不妨倍增找到 \(u\) 在 Kruskal 重构树上的最浅祖先，使得它包含的所有叶子不是都和 \(u\) 在同一连通块。
考虑把 Kruskal 重构树拍平到序列上，那么每个点的子树管辖 dfn 序在 \([l_i, r_i]\) 中的叶子。设 \(f_i\) 为 \(i\) 所在连通块的代表元，\(g_i\) 为 dfn 序为 \(i\) 的点，\(d_i\) 为最大的 \(j\) 使得 \(\forall k \in [j, i], f_{g_k} = f_{g_i}\)，也就是说 \(g_{d_i - 1}\) 是 \(i\) 在 dfn 序上往左第一个与 \(g_i\) 不在同一连通块的点。
考虑倍增到 \(u\) 的一个祖先 \(v\) 后，如何判定 \(v\) 子树管辖的叶子不是都和 \(u\) 在同一连通块，并且如果这个条件满足，还要找到这样的一个叶子。如果 \(g_{r_v}\) 不和 \(u\) 在同一连通块，那么 \(g_{r_v}\) 即为所求。否则，dfn 序在 \([d_{r_v}, r_v]\) 中的叶子都和 \(u\) 在同一连通块，若 \(d_{r_v} > l_v\)，那么 \(g_{d_{r_v} - 1}\) 即为所求，否则 \(v\) 不满足条件。
但是有个问题，因为我们求的是补图的最小生成树，所以找到的边不能是原图上有的边。考虑判定 \(v\) 是否满足条件时，对于所有 \(u\) 在原图上连出去的边 \((u, w)\)，\(l_w\) 把 \([l_v, r_v]\) 分成了 \(O(deg_u)\) 个小区间。因为 \(O(\sum deg_u) = O(m)\)，所以我们可以暴力找到 \(O(deg_u)\) 个小区间，再按照上面的方法判定即可。
时间复杂度 \(O(m (\log^2 n + \log m))\)。