记录编号	344646	评测结果	AAAAAAAAAAAAAAAAAAAA
题目名称	[NOI 2011]道路修建	最终得分	100
用户昵称	Go灬Fire	是否通过	通过
代码语言	C++	运行时间	10.546 s
提交时间	2016-11-10 14:12:14	内存使用	43.83 MiB

#include<cstdio>
#include<algorithm>
#include<cstring>
#include<iostream>
#include<cmath>
using namespace std;
#define LL long long
#define Begin freopen("noi2011_road.in","r",stdin);freopen("noi2011_road.out","w",stdout);
#define End fclose(stdin);fclose(stdout);
const int maxn=1000000+1000;
struct Edge{
	int from,next,to,dis;
}e[maxn<<1];
int len,head[maxn],root[maxn],size[maxn],deep[maxn];
int n;
void Insert(int x,int y,int z){
	len++;e[len].to=y;e[len].from=x;e[len].next=head[x];e[len].dis=z;head[x]=len;
}
void Init();
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;
}
inline void Dfs(int x){
	size[x]=1;
	for(int i=head[x];i;i=e[i].next){
		int j=e[i].to;
		if(root[x]!=j){
			root[j]=x;deep[j]=deep[x]+1;
			Dfs(j);
			size[x]+=size[j];
		}
	}
}
inline LL Calc(int x,int y,int length){
	if(deep[x]>deep[y])swap(x,y);
	LL tot=0;
	tot+=1ll*length*1ll*abs(size[1]-size[y]-size[y]);
	//printf("<<%d %d  %d %d>>\n",x,y,length,tot);
	return tot;
	
}
int main(){
	int __size__=64<<20;
	char *__p__=(char*)malloc(__size__)+__size__;
	__asm__("movl %0, %%esp\n"::"r"(__p__));
    Begin;
    Init();
    getchar();getchar();
    End;
    return 0;
}
inline void Init(){
	scanf("%d",&n);
	for(int i=1;i<n;i++){
		int x=Read(),y=Read(),z=Read();
		Insert(x,y,z);Insert(y,x,z);
	}
	Dfs(1);
	//for(int i=1;i<=n;i++)printf("<<%d %d>>\n",i,size[i]);
	LL ans=0;
	for(int i=1;i<=len;i+=2){
		int u=e[i].from,v=e[i].to;
		ans+=Calc(u,v,e[i].dis);
		//printf("%d %d %d %d %d\n",u,v,e[i].dis,size[u],abs(2*size[u]-size[1]));
		//ans+=abs(size[u]-(size[1]-size[u]))*e[i].dis;
	}
	printf("%lld\n",ans);
}
/*
6 
1 2 1
1 3 1
1 4 2
6 3 1
5 2 1
*/