[JSOI2008] 最小生成树计数

我们考察 Kruskal 算法的过程：

将所有边按照边权分为一些等价类，按照边权从小到大，依次将等价类中所有边在保证无环的基础上尽量加到森林中，直到构成一棵树。

注意到等价类内部是无序的，那么同一等价类中的不同选法就导致了最小生成树的不同树形。

那么由此看出，在加入所有边权小于 $w$ 的等价类之后，等价类中不存在加入森林后能够使两棵树连接在一起，改变其连通性的边。此时的树的连通情况和将这些等价类中的所有边全部加入的图是一样的，也即，不论等价类内部如何选边，此时树的连通情况是确定的。

这也就是说，不同等价类之间选边方案是独立的。所以我们分别考虑每个等价类的选边方案。

加入所有边权小于 $w$ 的等价类之后，将已经形成的连通块缩点，边权等于 $w$ 的等价类的选边方案数可以运用矩阵树定理简单地求得。