走廊泼水节

题目描述：

给定一颗n个节点的树，你需要增加若干条边，把这颗树扩充为完全图，并满足图的最小生成树是唯一的且是原树，问增加的边的权值总和最小是多少

思路：

完全图指的是图中的任意两点之间都有一条边相连

因为给定的是一棵树，树上的每个点都至少连一条边，对于每个点，与它相邻所有的边的权值一定有一个最小值，我们记做minx，对于完全图，一个点i要和其他的每个点j都连一条边，为了保证最小生成树是原树且最小，则新连的边的权值一定是max(minx[i], minx[j]) + 1

但是如果我们直接暴力枚举是肯定会TLE的,得换个方法计算

我们可以对边权从小到大进行排序，将每个点看成一个完全图，每次的边都会连接两个完全图，此时需要的边的权值就是当前枚举的这个边的权值 + 1，那将两个完全图变成一个连通图需要连连多少条边？假设完全图的大小是num,则需要连接num[a] * num[b]-1条边，减1是因为减掉的是当前枚举的这条树上的边

所以可以用并查集来维护连通块大小，类似于最小生成树

//Work by: Chelsea
#include <bits/stdc++.h>
using namespace std;

#define endl '\n'
#define inf 0x3f3f3f3f
#define mod 1000000007
#define sd(n) scanf("%d",&n)
#define sdd(n,m) scanf("%d %d",&n,&m)
#define m_p(a,b) make_pair(a, b)
#define mem(a,b) memset((a),(b),sizeof(a))
#define rep(i,a,b) for(int i=(a);i<=(b);i++)
#define io ios::sync_with_stdio(false); cin.tie(0); cout.tie(0)

typedef long long ll;
typedef pair <int,int> pii;

#define MAX 300000 + 50
int n, m, k, op;
struct ran{
    int x, y, z;
    bool operator < (const ran &a)const{
        return z < a.z;
    }
}tr[MAX];
int fa[MAX];
int cnt[MAX];
inline int getfa(int x){
    return fa[x] == x ? x : fa[x] = getfa(fa[x]);
}

void work(){
    cin >> n;
    for(int i = 1; i <= n; ++i){
        fa[i] = i;
        cnt[i] = 1;
    }
    for(int i = 1; i < n; ++i){
        cin >> tr[i].x >> tr[i].y >> tr[i].z;
    }
    sort(tr + 1, tr + n);
    ll ans = 0;
    for(int i = 1; i < n; ++i){
        int xx = getfa(tr[i].x);
        int yy = getfa(tr[i].y);
        ans += (cnt[xx] * cnt[yy] - 1) * (tr[i].z + 1);
        fa[xx] = yy;
        cnt[yy] += cnt[xx];
    }
    cout << ans << endl;
}


int main(){
    io;
    int tt;cin>>tt;
    for(int _t = 1; _t <= tt; ++_t){
        work();
    }
    return 0;
}