给定一棵N个节点的树，要求增加若干条边，把这棵树扩充为完全图，并满足图的唯一最小生成树仍然是这棵树。求增加的边的权值总和最小是多少。
输入格式 第一行包含整数t，表示共有t组测试数据。 对于每组测试数据，第一行包含整数N。 接下来N-1行，每行三个整数X,Y,Z，表示X节点与Y节点之间存在一条边，长度为Z。
输出格式 每组数据输出一个整数，表示权值总和最小值。 每个结果占一行。
数据范围 N≤6000,Z≤100
输入样例： 2 3 1 2 2 1 3 3 4 1 2 3 2 3 4 3 4 5 输出样例： 4 17 #pragma GCC optimize(2) #include<bits/stdc++.h> using namespace std; const int N = 6e3 + 10; int ans; struct node { int x, y, z; bool operator<(const node &a) const { return z < a.z; } } e[N]; int num[N], fa[N]; int t, n; int get(int x) { return x == fa[x] ? x : (fa[x] = get(fa[x])); } void merge(int x, int y) { num[y] += num[x]; fa[x] = y; } void init() { for (int i = 1; i <= n; i++) fa[i] = i, num[i] = 1; ans = 0; } void read() { scanf("%d", &n); for (int i = 1; i <= n - 1; i++) scanf("%d%d%d", &e[i].x, &e[i].y, &e[i].z); } void solve() { sort(e + 1, e + n); for (int i = 1; i <= n - 1; i++) { int x = get(e[i].x), y = get(e[i].y); if (x == y)continue; ans += (e[i].z + 1) * (num[x] * num[y] - 1); merge(x, y); } printf("%d\n", ans); } int main() { cin >> t; while (t--) { read(); init(); solve(); } return 0; }