题目描述

给定一棵 N
个节点的树，要求增加若干条边，把这棵树扩充为完全图，并满足图的唯一最小生成树仍然是这棵树。

求增加的边的权值总和最小是多少。

注意： 树中的所有边权均为整数，且新加的所有边权也必须为整数。（新加的边的权重自己定）

思路（自己的想法，想了很久为什么要先排序）

这里是全思路的题解过程和证明，我的一点自己的想法从“证明”里的3 开始。

题目大意见题目的描述，做法是：
1.先把每个点视为孤立的点，也就是一个点就是一个“团”，直接用并查集维护
2.对于给定最小生成树(后简称“树”)的每一条边（后简称“树边”），先按权值排序，按从小到大的顺序扫描每一条边：起始点a,终点b，权值w，后简称(a, b, w)，对于(a, b, w)，取出a和b所在的“团”，对于这两个“团”中的每一个除了（a,b） 之外的点对 （a1,b1），在其中添加上一条权为 w+1 的边，总共添加 cnt[a] * cnt[b] - 1 条边，cnt[a] 表示a所在的“团”的元素数量。
3.每扫描完一条边（a,b,w），则把a和b所在的“团”合一，用并查集同样很好维护这个过程，这时候a和b所在的“团”即是一个完全图。这时候有个推论：对于每个过程中，一个“团”中若包含一条“树”边（a,b,w），则必在之前有一次迭代中，迭代到了这条“树”边（a,b,w）。 当扫描完树中的所有边时，这个完全图恰好包含所有的点，则该完全图就是所求。

该做法的正确性证明：
1.按照所给的顺序，一定可以把该生成树扩充成完全图
2.在每一次迭代的过程中，添加的边权 w+1 一定是最小值了（通俗来说就是，这样做已经把新加的边的边权压缩的最小了，再小一点都一定带来新的最小生成树，但并不说明目前的做法一定不会带来最小生成树），怎么证明这一条，yxc的课里讲的很清楚，不过多赘述了
3.我真正想说的：就是该做法中，一定不会带来新的最小生成树，这个证明感觉yxc讲的不是很清楚，现说明我的想法：
用数学归纳法加kruskal算法的性质：
数学归纳法：假设在迭代到一条树边（a,b,w）的 上一条 “树边” （称“pre”）之后，（此时称“1”状态），kruskal会选择原来的最小生成树，现证：迭代完（a,b,w）后，kruskal依然会选择原来的最小生成树。
考虑kruskal的过程：当我们在“1”状态时，会选择pre，然后是w边，然后的边next……都是来自原来树的边。
迭代完(a,b,w)后，我们只是加了若干条权值为 w+1 的边，则kruskal选择过程，直到选了pre和w边的选择都是不会变化的，即kruskal选择直到w边这一过程都和“1”状态的时候一模一样，因为我们做该轮迭代没有加入权值小于等于w的边。此时kruskal继续扫描：虽然我们加入了若干条权为 w+1 的边，但是此时a和b已经被w联通，a和a所在的“团”和b和b所在的“团”在kruskal下都是联通的，因为kruskal之前扫描过的“树”边一定能联通a所在的“团”（这和我们从小到大迭代的过程有关：关注a“团”形成，结合的过程： 所以a团中的所有元素一定有pre及其之前的“树”边相连）和b所在的“团”。
一旦又选了任何一个我们加入的 w+1 的边，该边都会连接a和b所在的“团”成“环”，所以kruskal不会选这几条边，然后此时图中剩下的边，和“1”状态的kruskal选择完（a,b,w）后剩下的边，一模一样，所以kruskal会按照和原来一模一样的方式进行选择。综上，在迭代完（a,b,w）后，kruskal的选择和“1”状态的时候kruskal的选择一模一样，即都是选择了原来的最小生成树，证毕。