贪心，对于2个连通块合并时，应将所有边设成c+1，剩下的最小生成树模板

#include <iostream>
#include <cstring>
#include <algorithm>
using namespace std;
const int N = 6010;
int n;
int p[N];
struct Edge{
    int a,b,c;
}edge[N];
int Size[N];
bool cmp(Edge x,Edge y){
    return x.c < y.c;
}
int find(int x){
    if(p[x] != x) p[x] = find(p[x]);
    return p[x];
}
int main()
{
    int t;
    scanf("%d",&t);
    while(t -- ){
        int ans = 0;
        scanf("%d",&n);
        for(int i=1;i<=n;i++) p[i] = i,Size[i] = 1;
        for(int i=1;i<n;i++){
            int a,b,c;
            scanf("%d %d %d",&a,&b,&c);
            edge[i] = {a,b,c};
        }
        sort(edge + 1,edge + n,cmp);
        for(int i=1;i<n;i++){
            int a = edge[i].a,b = edge[i].b,c = edge[i].c;
            a = find(a),b = find(b);
            if(a != b){
                ans += (Size[a] * Size[b] - 1) * (c + 1);
                Size[b] += Size[a];
                p[a] = b;
            }
        }
        printf("%d\n",ans);
    }
    return 0;
}