记录编号	267953	评测结果	AAAAAAAAAA
题目名称	[HZOI 2016]仲夏之夜	最终得分	100
用户昵称	洛克索耶夫	是否通过	通过
代码语言	C++	运行时间	0.161 s
提交时间	2016-06-11 19:34:01	内存使用	2.60 MiB

#include<bits/stdc++.h>
using namespace std;

int Read()
{
	int a = 0, minus = 1;
	char ch = getchar();
	if(ch == '-')       minus = -1;
	while(ch < '0' || ch > '9'){
		ch = getchar();
		if(ch == '-')	minus = -1;
	}
	while(ch >= '0' && ch <= '9'){
		a = a * 10 + ch - '0';
		ch = getchar();
	}
	return a * minus;
}

int n;
long long tot = 0, sum[100010];
int root[100010];//sum[i]:根节点为i的集合的元素个数 
struct EDGE{
	int from, to, w;
	EDGE()
	{
		from = to = w = 0;
	}
}edges[100010];

int FindRoot(const int& a)
{
	if(root[a] != a)	root[a] = FindRoot(root[a]);
	return root[a];
}

inline int Union(const int& a, const int& b)
{
	int ra = FindRoot(a), rb = FindRoot(b);
	root[rb] = ra;
	sum[ra] += sum[rb];
	sum[rb] = sum[ra];
}

inline long long cmp(const EDGE& a, const EDGE& b)
{
	return a.w < b.w;
}

int main()
{
	freopen("summer.in", "r", stdin);
	freopen("summer.out", "w", stdout);
	n = Read();
	for(int i = 1; i < n; i++){
		edges[i].from = Read(); edges[i].to = Read(); edges[i].w = Read();
		tot += edges[i].w;
	}
	for(int i = 1; i <= n; i++){
		sum[i] = 1; root[i] = i;
	}
	
	sort(edges + 1, edges + n, cmp);
	//for(int i = 1; i < n; i++)	printf("%d  ", edges[i].w);
	for(int i = 1; i < n; i++){
		int from = edges[i].from, to = edges[i].to;
		int f1 = FindRoot(from), f2 = FindRoot(to);
		/*----------
		两个集合连边连成完全图,边权应该是比已有的大,因为给出的是最小生成树
		两个集合之间(及之内)所有点都连边, 有(sum1 * sum2 -1)条新的边需要连上,因为那一条最短的边已经给出来了
		新边边权尽可能小,是已给出的边的边权+1
		----------*/
		//printf("sum[%d]:%d	sum[%d]:%d\n", from, sum[from], to, sum[to]);
		//printf("edges[i].w:%d\n", edges[i].w);
		tot += ((long long)sum[f1] * sum[f2] - 1) * (edges[i].w + 1);
		//printf("sum[from] + sum[to] - 1:%d  ", sum[from] + sum[to] - 1);
		//printf("tot:%d\n", tot);
		Union(from, to);
	}
	
	printf("%lld", tot);
	fclose(stdin);
	fclose(stdout);
	return 0;
}
/*
4
1 2 1
3 4 3
2 4 2
*/