记录编号	281867	评测结果	AAAAAAAAAA
题目名称	[HZOI 2016]仲夏之夜	最终得分	100
用户昵称	AntiLeaf	是否通过	通过
代码语言	C++	运行时间	0.170 s
提交时间	2016-07-12 13:52:26	内存使用	2.20 MiB

#include<cstdio>
#include<cstring>
#include<algorithm>
using namespace std;
const int maxn=100010;
struct edge{
	int x,y,dis;
	bool operator<(const edge &x)const{
		return dis<x.dis;
	}
}e[maxn];
long long rekruskal();
int findroot(int);
void merge(int,int);
int prt[maxn],a[maxn];
int n;
long long ans=0ll;
int main(){
	freopen("summer.in","r",stdin);
	freopen("summer.out","w",stdout);
	scanf("%d",&n);
	for(int i=1;i<n;i++){
		scanf("%d%d%d",&e[i].x,&e[i].y,&e[i].dis);
		ans+=(long long)e[i].dis;
	}
	printf("%lld",rekruskal());
	fclose(stdin);
	fclose(stdout);
	return 0;
}
long long rekruskal(){
	int x,y;
	for(int i=1;i<=n;i++){
		prt[i]=i;
		a[i]=1;
	}
	sort(e+1,e+n);
	for(int i=1;i<n;i++){
		x=findroot(e[i].x);
		y=findroot(e[i].y);
		ans+=(long long)(e[i].dis+1)*(long long)(a[x]*a[y]-1);
		merge(x,y);
	}
	return ans;
}
int findroot(int x){
	if(prt[x]!=x){
		prt[x]=findroot(prt[x]);
	}
	return prt[x];
}
void merge(int x,int y){
	int rx=findroot(x),ry=findroot(y);
	if(rx==ry)return;
	prt[rx]=ry;
	a[ry]+=a[rx];
}
/*
4
1 2 1
2 4 2
3 4 3
Answer:
17
*/