https://ac.nowcoder.com/acm/contest/874/G

题意：给定一颗树，定义两点的weight为两点路径最大边权值。求任意两点的weight之和。
思路：一开始自然的思路，将边从大到小排，这条边的贡献次数是左结点个数 ∗ * ∗右结点个数，依次删边，并维护子树结点个数，但是这样子难以实现。
我们反过来想，变成将边从小到大排，依次加边计算，维护连通性和子树大小，用并查集 s o <mtext>   </mtext> e a s y so\ easy so easy

//华工软院H
#include<bits/stdc++.h>
using namespace std;
#define maxn 1000000+1000
#define ull unsigned long long
 
int T,n,p[maxn],sz[maxn];
ull ans;
struct Edge{
    int u,v,w;
    bool operator < (Edge x){
        return w<x.w;
    }
}e[maxn];
 
int findset(int x){return x==p[x]?x:p[x]=findset(p[x]);}
 
int main()
{
  // freopen("input.in","r",stdin);
    cin>>T;
    while(T--)
    {
        cin>>n;
        for(int i=1;i<n;i++)scanf("%d%d%d",&e[i].u,&e[i].v,&e[i].w);
        sort(e+1,e+n);
        for(int i=1;i<=n;i++)p[i]=i;
        for(int i=1;i<=n;i++)sz[i]=1;
        ans=0;
        for(int i=1;i<n;i++)
        {
            int u=findset(e[i].u),v=findset(e[i].v);
            ans+=(ull)sz[u]*sz[v]*e[i].w;
            sz[u]+=sz[v];
            p[v]=u;
        }
        cout<<ans<<"\n";
    }
    return 0;
}