using namespace std;
typedef long long ll;
struct Edge
{
int u,v;
ll w;
}es[20005];
bool operator<(Edge e1,Edge e2)
{
return e1.w < e2.w;
}
int par[20005],tot[20005];
ll res;
void prep()
{
for(int i=1;i<=20005;i++)
{
par[i]=i;
tot[i]=1;
}
}
int fnd(int x)
{
if(x==par[x])
return x;
return par[x]=fnd(par[x]);
}
void unite(int u, int v,ll w)
{
int a=fnd(u);
int b=fnd(v);
res+=((tot[a]*tot[b]-1)*(w+1));
par[b]=a;
tot[a]+=tot[b];
}
int main()
{
int k;
scanf("%d",&k);
for(int i=1;i<=k;i++)
{
int n;
scanf("%d",&n);
for(int i=1;i<=n-1;i++)
{
scanf("%d%d%lld",&es[i].u,&es[i].v,&es[i].w);
}
sort(es,es+n);
prep();
for(int i=1;i<=n-1;i++)
{
res+=es[i].w;
unite(es[i].u,es[i].v,es[i].w);
}
printf("%lld\n",res);
res=0;
for(int i=1;i<=20005;i++)
{
es[i].u=0;es[i].v=0;es[i].w=0;
par[i]=0;tot[i]=0;
}
}
return 0;
}
此题根据最小生成树的概念：给了构成最小生成树的边，就说明它是那一步中(u,v)最小的，所以其它的至少大于，因为是完全图，所以两个集合间必定两两连边。综上，就按照构成最小生成树的步骤来，中途加入统计需要加的和