哥我真的佩服你了，，，
你说物理老师上完课说的给一两天整理的意思又没有可能是指拿时间整理一下然后等老师来讲，
而不是做完作业直接开跑看课，然后让大家追赶你的步伐，，，
有点流汗了，感觉现在一天学了好多脑子要爆掉了，然后我还得快点做作业来跟上你看课的速度，，，
哥我错了，我是菜比行吗，，，
在您的引领之下，仅用四天就把物理补完了开始要回去上物理课了。
甚至是只回去上物理，有点搞笑了。
但是又要回班上了，我要玉玉了。
实际上 boruvka 是十分优美的一个东西。
虽然往往只直接把复杂度当作 \(\mathcal{O}(f(n, m)\log n)\)（\(f(n, m)\) 通常就是一个关于 \(n, m\) 的多项式，视题目及做法而定），但是还是要考虑下为什么的。
这是因为在最劣情况下如果每次找最小边都是双向边，所以才会使得每次连通块数 \(/ 2\) 的，轮数 \(\mathcal{O}(\log n)\)。
但是实际上抛弃死板的复杂度，从每一步去入手能得到更优美的性质。
其实也就是去深究一下每一步缩连通块的情况。
例题：Codeforces 2041N（口胡还在发力）。
这种差不多的完全图，肯定是还要考虑下 boruvka 的。
然后分析 boruvka 第一轮点 \(i\) 找到的对应的最短边 \((i, j)\) 的 \(j\) 的性质。
那么因为边权是 \(a_i + a_j\) 的形式，那就是要最小化 \(a_j\)。
定义 \(S_i = \{1, 2, \cdots, n\} - \{j | (i, j)\in E\} - \{i\}\)（\(E\) 为被删掉的边集），那么 \(j\) 肯定满足 \(j\in S_i, a_j = \min_{k\in S_i}(a_k)\)。
于是一个直观的过程就是先按 \(a_i\) 从小到大排序。
对于每一个 \(i\)，\(j = 1\) 开始往后扫，直到 \(j\not = i, (i, j)\not \in S\)，那么第一轮的连边就是 \((i, j)\)。
这个时候令 \(b_i = j - 1\)，那么应当有 \(\sum\limits_{i = 1}^n b_i\le |S| = m\)，那么这说明了暴力扫的复杂度是对的（均摊）且 \(b_i\) 只会有 \(\mathcal{O}(\sqrt m)\) 种本质不同值。
（实际上有点小问题，因为忽略掉了 \(i = j\) 时凭空多出的一条被删的边，但是实际上这个情况也只会出现 \(\mathcal{O}(\sqrt{m})\) 次，是 \(\mathcal{O}(\sqrt{m + \sqrt m})\)，但是直接分析成 \(\mathcal{O}(\sqrt{n + m})\) 问题也不大。）
那么这说明了在第一轮的缩点后，实际上的连通块只会有 \(\mathcal{O}(\sqrt m)\) 个（连通块应当关于 \(b_i\) 是个类菊花的样子，\(b_i\) 为根），而且 \(\operatorname{deg}_i > 1\) 的点此时只会有 \(\sqrt{m}\) 个。
于是说在后面的 \(\mathcal{O}(\sqrt{m})\) 个连通块间跑出的最小生成树也只会有 \(\mathcal{O}(\sqrt{m})\) 条边，那么在这一阶段产生的 \(\operatorname{deg}_i > 1\) 的点的数量也是 \(\mathcal{O}(\sqrt m)\) 级别的。
于是整合起来，\(\operatorname{deg}_i > 1\) 的点的数量是 \(\mathcal{O}(\sqrt m)\) 的。
那么对于 \(\operatorname{deg}_i = 1\) 的叶子，最小生成树内删掉了对树的形态没有影响。
于是只需要对于 \(\mathcal{O}(\sqrt m)\) 个非叶子的点直接删掉重新跑一遍最小生成树就行了。
当然这只是大体思路，还需要讨论下细节问题。
Q：如何 \(\mathcal{O}(n + m)\) 求最小生成树？
首先第一轮的 boruvka 找最小值是 \(\mathcal{O}(n + m)\) 的，排序可以用基数排序做到 \(\mathcal{O}(n)\)，后面的连边可以在最后连出的环找一下环上最大权边，断掉即可，也是 \(\mathcal{O}(n)\) 的（实际上想直接用并查集 \(\alpha(n)\) 应该也是可以的吧）。
那么对于后面 \(\mathcal{O}(\sqrt m)\) 个连通块的最小生成树只需要在 \(\mathcal{O}(n + m)\) 内找到两两连通块间的最小边权，然后跑 \(\mathcal{O}(n^2 + m)\) 的 prim 就可以了（这里的 \(n, m\) 指的是缩完连通块的图的点数边数，所以复杂度应是 \(\mathcal{O}(m)\) 的）。
Q：那如何 \(\mathcal{O}(n + m)\) 找到两两连通块间的最小边权。
好问题……
首先可以在块内先按 \(a_i\) 排好序。
首先一个暴力的想法是对于每个点都找一下每个连通块的最小值，这个依然均摊分析到 \(\mathcal{O}(n + m)\)。
最后在连通块内合并信息，但是这样就 \(\mathcal{O}(m\sqrt{m})\) 了……
考虑到块内其实还是有很多信息是无用的。
考虑直接枚举两个块，让其中一个块 \(a_i\) 从小到大遍历 \(i\)，那么对应在另一个块找到于其的最小权 \(a_j\)。
注意到的是因为 \(a_i\) 不降，那么如果第一个块后面才枚举到的 \(a_k\ge a_i\)，实际上在第二个块枚举到 \(j\) 之前就可以了，因为 \(a_k + a_j\ge a_i + a_j\)，\(j\) 往后还更大。
实际上一个更偷懒的想法是如果找到 \(a_i\) 能和第二个块的最小值连边就直接不往后枚举了，正确性显然，就是上面说到的弱化。
考虑分析复杂度，那么可以拆分为，跳过（被删掉）的边数 + 在第一个块遍历到的点数（对于这些点确定一条边出来）。
那么被跳过的边肯定是不超过 \(m\) 条的。
对于遍历到的点数，拆分成，前缀不能与另一个块最小值有连边的点数 + 与另一个块最小值有连边的点数。
对于第一部分，依然是均摊分析被跳过的边，是 \(\mathcal{O}(m)\) 的；对于第二部分，两个连通块间只会存在一次，因为连通块数是 \(\mathcal{O}(\sqrt{m})\) 的，最后也是 \(\mathcal{O}(m)\) 的。
于是最后时间复杂度 \(\mathcal{O}((n + m)\sqrt{m})\)，看起来好像就完结撒花了/庆祝。
实际上实现可能还是有点难度的，加上我是口胡哥，就没有代码了。
byd 差点给删了，吓死我了。
我严重怀疑这题是那位 tmt514 出的。
之前 boruvka 就搜到过他的文章（其实是 boruvka 分治，但是我现在都还没看）。
而且里面有个专门的最小生成树板块。
而且里面还有个 Borůvka-Prim 演算法 感觉就是和这题大致过程一样，先 boruvka 在 prim 阿。
参考链接：https://tmt514.github.io/algorithm-analysis/minimum-spanning-tree/boruvka-prim.html
突然发现似乎我的摆都是因为记性不好。
回到上文，boruvka 分治感觉在序列上没有什么用阿。
感觉这个结构还不是很好维护，不如在序列上面建 kruskal 树。
但是序列上的 kruskal 树是不是就是笛卡尔树来着。
我草我现在才发现，是不是没救了。