最小树形图

之前没涉及到，这个贪心还挺牛的。

最小树形图定义在有向图上，即所有作为子图出现的叶向树的最小边权和。

解决最小树形图的算法是朱刘算法，暴力复杂度是 $\mathcal O(nm)$ ，tarjan 优化后可以做到 $\mathcal O(m+n\log n)$ 。

~~你说的对，但是朱 = 刘。~~

考虑树形图的性质，除了根节点，每个点都有唯一的入边（之后讨论入边时，我们钦定一个根 $r$ ，不考虑 $r$ ）。

我们直接对于每个点选择它最小的入边！如果该图没有环，这一定是最小树形图之一。

如果该图有环，显然环上至多一条边没用，我们需要把一条环边换成指向环的边，我们直接将环缩点！然后把指向这个环的边权减掉入边最小值，删掉环内所有边，答案加上环边，然后递归，至多 $n$ 轮，复杂度 $\mathcal O(nm)$ 。

这个递归是很妙的，让后人解决此刻解决不了的问题。

暴力即可通过【模板】最小树形图。

实现上，我们把不在环中的点视作在自环中，然后每条边都减去出点的最小边权，每轮所有的环是下一轮所有的点，所有边可以直接使用边表存储（全局数组）。

在邻接矩阵上做上述过程，合并两个点只需 $\mathcal O(n)$ 的代价，而最小边只有被合并的点有变化，重新求一遍即可，复杂度 $\mathcal O(n^2)$ 。

tarjan 优化可以看作有向图版本的 prim，而暴力朱刘可以看作 Boruvka。

外流程更改为枚举一个点，然后不断跳最小入边，出现环则缩。

使用任意一种支持打全局标记的可并堆维护即可，删除环内的边可以惰性删除。

建虚点 $0$ ，向其他点连 $\infty$ 边，答案就是以 $0$ 为根的最小树形图的答案减掉 $\infty$ ，如果选了超过两条 $\infty$ 说明无解。

给定根判无解同理，根向其他点连 $\infty$ 边，选了就无解。