算法1

/*
   完全图和连通图之间的区别:
   完全图: 完全图是指任意两个结点之间都有一条边相连,也就是节点两两相连。
   连通图：连通图是指任意两个节点之间都有一个路径连接 
   要扩充为完全图,说明要使得题中给的每个条件满足上述的要求。
   题目链接 : https://www.acwing.com/problem/content/348/
*/ 
#include<iostream>
#include<algorithm>
#include<cstring>
#include<cstdio>
#include<string.h>
#include<limits.h>
#include<vector>
#include<deque>
#include<queue>
#include<stack>
#include<map>
#include<set>
using namespace std;
const int maxn = 6e3 + 10;
typedef long long LL;
struct node {
    int x,y,z;
}edge[maxn];
int s[maxn],fa[maxn];       // fa[maxn] 表示并查集的父子关系, s[maxn] 表示每个集合的大小(刚开始每个集合都只包括本身,所以初始化为 1 ) 
int t,n;
LL res = 0;
int main(void) {
    void solve(); 
    scanf("%d",&t);
    while(t --) {
        scanf("%d",&n);
        for(int i = 1; i < n; i ++) {
            scanf("%d%d%d",&edge[i].x,&edge[i].y,&edge[i].z);
        }
        res = 0;
        solve();
        printf("%lld\n",res);
    } 
    return 0;
} 
bool cmp(node a,node b) {
    return a.z < b.z;
}
int findx(int x) {
    return x == fa[x] ? x : fa[x] = findx(fa[x]);
}
void solve() {
    sort(edge + 1,edge + n,cmp);                     // 这里需要排序的是 n - 1个,不再是 n 个(因为有 N - 1条边) 
    for(int i = 1; i <= n; i ++) {
        fa[i] = i,s[i] = 1; 
    }
    for(int i = 1; i < n; i ++) {
        int xx = findx(edge[i].x);
        int yy = findx(edge[i].y);
        if(xx == yy) continue;
        fa[xx] = yy;
        res += (long long)(edge[i].z + 1) * (s[xx] * s[yy] - 1); // 强制转换,使得两边的类型一致 (将两个集合进行合并,形成完全图,就需要(s[xx] * s[yy] - 1)条边 )
                                                                 // 并且这里还要满足原先的一直是最小生成树,所以我要保证原先的边的权值是最小的 
        s[yy] += s[xx];                                          // 扩充其中一个集合 
    } 
    return ;
}