-
题目链接：
-
思路：
首先这需要一个推论：
“给定一张无向图,若用(k(k<n-1))条边构成一个生成森林(可以理解为多个互不相通的生成树),再从剩下的(m-k)条边中选出(n-1-k)条边构成改该图的最小生成树,则这(m-k)条边中一定包含连接两个不相连生成森林的最小边权的两点”
这个推论是由这个定理得到：
“一张无向图的最小生成树一定包含边权最小的那条边”，这个定理可以很容易地用反证法证得。
那么我们就可以开始了,若连接两个不连通的生成森林最小边权为(e),根据推论,想要让它变成一张完全图而最小生成树保持不变,当然是让剩下的点相连边的权值为(e+1)。
那么让这两个生成森林变成完全图则需要((e+1)*(size[A]*size[B]-1)),(size[K])为以K为父节点的生成森林所含的点数，减去1是因为两个之中已经有一条边权为(e)的边
根据贪心的思想，我们显然所有边从小到大排序，如果两顶点不在一个森林里，那么合并，加入贡献。
-
代码(话说并查集路径压缩一开始写错了，查了好久的错，真是太蒻了)：
#include <iostream>
#include <cstdio>
#include <cstdlib>
#include <cstring>
#include <algorithm>
#include <cctype>
#include <queue>
#include <vector>
#define ll long long
#define ri register int
using namespace std;
const int maxn=6005;
const int inf=0xfffffff;
struct Edge{
int f,t,val;
bool operator <(const Edge &b)const{
return val<b.val;
}
}edge[maxn];
int n,t;
ll ans=0;
int size[maxn],fa[maxn];
template <class T>inline void read(T &x){
x=0;int ne=0;char c;
while(!isdigit(c=getchar()))ne=c=='-';
x=c-48;
while(isdigit(c=getchar()))x=(x<<3)+(x<<1)+c-48;
x=ne?-x:x;
return ;
}
int get(int x){
if(fa[x]!=x)fa[x]=get(fa[x]);
return fa[x];//注意路径压缩写法
}
int main(){
int u,v,d;
read(t);
while(t--){
int ans=0;
memset(edge,0,sizeof(edge));
read(n);
for(ri i=1;i<n;i++)
read(edge[i].f),read(edge[i].t),read(edge[i].val);
sort(edge+1,edge+n);
for(ri i=1;i<=n;i++){fa[i]=i,size[i]=1;}
for(ri i=1;i<n;i++){
u=edge[i].f,v=edge[i].t,d=edge[i].val;
//cout<<u<<' '<<v<<endl;
u=get(u),v=get(v);
//cout<<u<<' '<<v<<endl;
if(u!=v){
fa[u]=v;
ans+=(d+1)*(size[u]*size[v]-1);
size[v]+=size[u];
}
}
printf("%d
",ans);
}
return 0;
}