好水（
铃在谷群说有线性mst的科技，然后就找了一篇来看。严格线性mst看起来很离谱，期望线性则还可以。它俩的难度大概类似于sa-is之于dc3?
如果我们现在有一个生成树，那么不在生成树上的边可能可以更新这个生成树，方法是把它在树上经过的路径上边权最大的边拿出来，尝试用它来替换。如果这个最大边比这条不在树上的边边权小(不包括相等)，我们称这条不在树上的边是重边，否则这条边是轻边。
引理 如果我们随机一个图的每条边选不选，选的概率是\(p\)，然后得到一个子图，然后以某种方式求出子图的mst。那么不在子图中的轻边只有期望\(\frac{n-1}{p}\)条。
证明 考虑Kru的过程，你发现一条边是轻边取决于比它边权小的边能不能让它的端点连起来，所以一条边是轻是重在处理它之前已经确定了，处理它之后不会改变。考虑这个确定它是否被选的随机数，在它是重边的时候表现如何没有任何影响，而轻边最终会被选\(n-1\)条，根据几何分布需要期望\(\frac{n-1}{p}\)条轻边才能选出这么多条，而选出来之后剩下的全是重边了，于是就证完了。
算法流程很简单。
-
跑两遍boruvka，并缩点。
-
以\(\frac{1}{2}\)的概率选中每条边，递归下去跑一个mst，记为\(T\)。
-
对于所有边，如果它在\(T\)的意义下是轻边则保留它，然后递归下去跑一个mst。
复杂度证明也很简单，留作练习（
呃完全就是每次期望折半，这也是为什么我们跑两遍别乳卡。
但是有一个问题，就是我们需要求一个链\(\max\)。考虑四毛子，我们跑一个lca，一个la，就结束了。我感觉lca不是很好维护信息，但是la可以。