https://www.luogu.com.cn/problem/P10928

My Code:

#include <bits/stdc++.h>
using namespace std;
int T, n;
int fat[6007], siz[6007];
int find(int x) { return (x == fat[x] ? x : fat[x] = find(fat[x])); }
class edge
{
public:
    int u, v, w;
};
vector<edge> e;
bool cmp(edge a, edge b)
{
    return a.w < b.w;
}
int ans = 0;
int main()
{
    // freopen(".in", "r", stdin);
    // freopen(".out", "w", stdout);
    cin >> T;
    while (T--)
    {
        cin >> n;
        for (int i = 1; i <= n; i++)
            fat[i] = i, siz[i] = 1;
        for (int i = 1; i < n; i++)
        {
            int u, v, w;
            cin >> u >> v >> w;
            e.push_back({u, v, w});
        }
        sort(e.begin(), e.end(), cmp);
        for (auto x : e)
        {
            int Fu = find(x.u);
            int Fv = find(x.v);
            if (siz[Fu] < siz[Fv])
                swap(Fu, Fv);
            if (Fu != Fv)
            {
                ans += (siz[Fu] * siz[Fv] - 1) * (x.w + 1);
                fat[Fv] = Fu;
                siz[Fu] += siz[Fv];
            }
        }
        cout << ans << '\n';
        ans = 0;
    }
    return 0;
}