给定一棵N个节点的树，要求增加若干条边，把这棵树扩充为完全图，并满足图的唯一最小生成树仍然是这棵树。
求增加的边的权值总和最小是多少。
注意： 树中的所有边权均为整数，且新加的所有边权也必须为整数。
输入格式
第一行包含整数t，表示共有t组测试数据。
对于每组测试数据，第一行包含整数N。
接下来N-1行，每行三个整数X,Y,Z，表示X节点与Y节点之间存在一条边，长度为Z。
输出格式
每组数据输出一个整数，表示权值总和最小值。
每个结果占一行。
数据范围
1 ≤ N ≤ 6000 , 1 ≤ Z ≤ 100 1≤N≤6000, 1≤Z≤100 1≤N≤6000,1≤Z≤100
输入样例：
2 3 1 2 2 1 3 3 4 1 2 3 2 3 4 3 4 5输出样例：
4 17分析：
完 全 图 ： 任 意 两 点 间 均 有 边 。 完全图：任意两点间均有边。 完全图：任意两点间均有边。
由 题 意 ， 每 次 合 并 两 个 连 通 块 时 ， 都 要 在 这 两 个 连 通 块 中 的 任 意 两 点 之 间 建 立 一 条 边 。 由题意，每次合并两个连通块时，都要在这两个连通块中的任意两点之间建立一条边。 由题意，每次合并两个连通块时，都要在这两个连通块中的任意两点之间建立一条边。
因 此 ， 每 个 连 通 块 内 一 定 是 一 个 完 全 图 。 合 并 时 ， 只 需 要 在 两 个 连 通 块 之 间 建 边 。 因此，每个连通块内一定是一个完全图。合并时，只需要在两个连通块之间建边。 因此，每个连通块内一定是一个完全图。合并时，只需要在两个连通块之间建边。
现 需 要 一 颗 最 小 生 成 树 扩 充 为 完 全 图 ， 我 们 假 设 树 中 两 个 节 点 为 i 和 j ， i 和 j 之 间 的 边 权 为 w i j 。 现需要一颗最小生成树扩充为完全图，我们假设树中两个节点为i和j，i和j之间的边权为w_{ij}。 现需要一颗最小生成树扩充为完全图，我们假设树中两个节点为i和j，i和j之间的边权为wij。
现 合 并 节 点 i 和 节 点 j 所 在 的 两 个 连 通 块 ， 假 设 新 增 的 边 权 为 w 。 现合并节点i和节点j所在的两个连通块，假设新增的边权为w。 现合并节点i和节点j所在的两个连通块，假设新增的边权为w。
① 、 w < w i j ， 那 我 们 用 边 w 来 替 换 w i j ， 就 能 得 到 一 颗 更 小 的 生 成 树 ， 矛 盾 。 ①、w<w_{ij}，那我们用边w来替换w_{ij}，就能得到一颗更小的生成树，矛盾。 ①、w<wij，那我们用边w来替换wij，就能得到一颗更小的生成树，矛盾。
② 、 w = w i j ， 若 我 们 用 w 来 替 换 w i j ， 就 能 得 到 一 颗 同 样 的 最 小 生 成 树 ， 与 题 意 最 小 生 成 树 唯 一 矛 盾 。 ②、w=w_{ij}，若我们用w来替换w_{ij}，就能得到一颗同样的最小生成树，与题意最小生成树唯一矛盾。 ②、w=wij，若我们用w来替换wij，就能得到一颗同样的最小生成树，与题意最小生成树唯一矛盾。
③ 、 w > w i j ， 满 足 题 意 。 ③、w>w_{ij}，满足题意。 ③、w>wij，满足题意。
要 使 得 新 增 边 权 最 小 ， 那 么 所 有 新 增 的 边 权 取 w + 1 即 可 。 要使得新增边权最小，那么所有新增的边权取w+1即可。 要使得新增边权最小，那么所有新增的边权取w+1即可。
这 样 每 次 合 并 两 个 连 通 块 a 和 b ， 代 价 为 S i z e [ a ] × S i z e [ b ] × ( w + 1 ) 。 这样每次合并两个连通块a和b，代价为Size[a]×Size[b]×(w+1)。 这样每次合并两个连通块a和b，代价为Size[a]×Size[b]×(w+1)。
其 中 S i z e [ a ] 表 示 节 点 a 所 在 连 通 块 中 节 点 的 数 量 。 其中Size[a]表示节点a所在连通块中节点的数量。 其中Size[a]表示节点a所在连通块中节点的数量。
可 见 ， 我 们 还 需 用 并 查 集 维 护 一 个 S i z e 数 组 。 可见，我们还需用并查集维护一个Size数组。 可见，我们还需用并查集维护一个Size数组。
代码：
#include<cstring> #include<iostream> #include<algorithm> using namespace std; const int N=6010; int T,n,m; int p[N],Size[N]; struct edge { int u,v,w; bool operator < (const edge &t) const { return w<t.w; } }E[N]; int Find(int x) { if(p[x]!=x) return p[x]=Find(p[x]); return p[x]; } int kruskal() { sort(E,E+m); int res=0; for(int i=0;i<m;i++) { int a=Find(E[i].u),b=Find(E[i].v),w=E[i].w; if(a!=b) { res+=(Size[a]*Size[b]-1)*(w+1); Size[b]+=Size[a]; p[a]=b; } } return res; } int main() { cin>>T; while(T--) { cin>>n; m=n-1; for(int i=0;i<=n;i++) p[i]=i,Size[i]=1; for(int i=0;i<m;i++) cin>>E[i].u>>E[i].v>>E[i].w; cout<<kruskal()<<endl; } return 0; }