Readme

3600.Maximize-Spanning-Tree-Stability-with-Upgrades

突破口是二分搜值。如果猜测全局最小的stability是T的话，尝试能否用最小生成树的方法构造出一棵树来。

当固定全局最小的stability是T之后，那么哪些edge能用哪些不能用就一目了然了。对于must的那些边，如果存在stability小于T的，那么显然无解。对于非must的边，如果2*stability<T，那么必然排除作为构造树的候选；反之就可以作为候选，同时我们需要根据2s和T的比较，标注这条边“是否需要upgrade”。

有了所有的候选边，我们就可以用Kruskal算法构造“最小生成树”。只不过这里优化的不是总边的权重，而是“upgrade的次数”。我们将所有边按照“是否需要upgrade”排序即可（其实就是0或者1），优先选用不需要upgrade的边实现更多的union。如果发现一个候选边的两个端点已经union在一起了，那么这条边其实就可以放心地舍弃而没有任何副作用。注意处理完所有的边之后还需要判断两点：是否恰好用到了n-1条边（否则说明可能有环），是否所有的点的find都相同（否则说明可能有不联通的区域）。