BZOJ2654 tree

题目蓝链

Solution

如果我们给所有白色边增加或减小边权,那么所选的白色边一定减少或增多。所以我们先将白边和黑边分别排好序,然后二分白色边的变化量\Delta,把所有的白边加上\Delta。跑最小生成树的时候,先有一个类似于归并排序的方法将黑边与白边合并,然后跑kruskal统计用了多少条白边,最后再对所有的白边减去\Delta即可。

阅读更多