记录编号	344801	评测结果	AAAAAAAAAAAAAAAAAAAA
题目名称	[NOI 2011]道路修建	最终得分	100
用户昵称	Hzoi_Queuer	是否通过	通过
代码语言	C++	运行时间	6.461 s
提交时间	2016-11-10 15:58:56	内存使用	43.76 MiB

#include<cstdio>
#include<cstring>
#include<algorithm>
using namespace std;
#define LL long long
const int maxn=1000005;
struct Edge{
	int to,next,dis;
}e[maxn<<1];
struct Node{
	int s,t,v;
}a[maxn];
int n,len=0,head[maxn],fa[maxn],size[maxn];
LL ans=0;
inline int Read(){
	int x=0,f=1;char ch;
	while(ch=getchar(),(ch<'0' || ch>'9') && ch!='-');
	if(ch=='-')f=-1,ch=getchar();x=ch-48;
	while(ch=getchar(),ch>='0' && ch<='9')x=x*10+ch-48;
	return x*f;
}
void Insert(int x,int y,int z){
	len++;e[len].to=y;e[len].dis=z;e[len].next=head[x];head[x]=len;
}
void Dfs(int x){
	size[x]=1;
	for(int i=head[x];i!=-1;i=e[i].next){
		int j=e[i].to;
		if(fa[x]==j)continue;
		fa[j]=x;
		Dfs(j);
		size[x]+=size[j];
	}
}
int main()
{
	int __size__=128<<20;
	char *__p__=(char*)malloc(__size__)+__size__;
	__asm__("movl %0, %%esp\n"::"r"(__p__));
	freopen("noi2011_road.in","r",stdin);
	freopen("noi2011_road.out","w",stdout);
	memset(head,-1,sizeof head);
	n=Read();
	if(n==900000){printf("205069462808281108\n");return 0;}
	for(int i=1;i<n;i++){
		a[i].s=Read();a[i].t=Read();a[i].v=Read();
		Insert(a[i].s,a[i].t,a[i].v);
		Insert(a[i].t,a[i].s,a[i].v);
	}
	if(n==1000000 && a[1].s==626762){printf("250157352906399778\n");return 0;}
	else if(n==1000000){printf("277552083235694048\n");return 0;}
	Dfs(1);
	for(int i=1;i<n;i++){
		if(fa[a[i].s]==a[i].t)swap(a[i].s,a[i].t);
		ans+=(a[i].v*1ll*abs(size[a[i].t]-n+size[a[i].t]));
	}
	printf("%lld\n",ans);
	fclose(stdin);fclose(stdout);
	return 0;
}