最小生成树相关性质

相关资料

个人觉得比较有用的。

  • 最小生成树的每一种权值边的数量是固定的。
  • 最小生成树的每一种权值边对联通块的变化是固定的。

第一个在相关资料里面有。

第二个可以考虑从小到大加边。

如果 $k - 1$ 成立,那么 $k$ 对当前生成森林的联通贡献是固定的,否则可以再连通。

那么我们换位思考一下,我们从小到大用乘法原理贡献合法方案,也就是贡献是独立的。

生成树计数一下即可。