生成树

题目描述

给你一棵带边权的树，这棵树是某个完全图唯一的最小生成树。问原来的完全图中所有边可能的最小边权和是多少。
完全图是任意两个点之间都有边相连的无向图。

解法

模拟最小生成树，用并查集实现。设当前边的左右端点为a,b，它们所在的点集大小为siz[a],siz[b]。

因为要把两个集合合并，总共需要siz[a]*siz[b]条边，除了当前边之外，其他边的权值=当前边的权值+1。然后合并集合，修改集合大小。