走廊泼水节.(最小生成树+思维)

题目大意：

给定一个树，你需要在这个树中添加若干条边，使得这颗树变成一个完全图，并且满足图的唯一最小生成树仍是这个树，问你最小添加的边权为多少？

思路：

不妨我们从头开始构造这个最小生成树。

假设我们当前加入的边为Edge(u,v,cost)，如果u所在的并查集为S(u)，v为S(v)，因为我们加的这条边，很明显是当前最小的（Kruskal的过程），那么如果我们要把原图变为一个完全图，则两个集合的任意两点都要加边，边的大小最小是多少呢？就是cost+1，因为如果存在x,y分别来自两个并查集，他们之间如果建立一条<=cost的边，最小生成树就会先链接(x,y)再链接(u,v)，很明显最小生成树会发生改变。

所以，我们模仿最小生成树的过程，每次合并两个并查集，答案就要加上(z+1)|s(u)s(v)-1|，这样保证最小生成树不变且加边最小。

#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
 
const int maxn=6000+10;
struct Edge{
    int u,v;
    ll cost;
    Edge(int u,int v,ll cost):u(u),v(v),cost(cost){}
};
vector<Edge>edges;
int cmp(const Edge a,const Edge b){
    return a.cost<b.cost;
}
int fa[maxn];
int sz[maxn];
i