记录编号	167362	评测结果	AAAAAAAAAAAAAAAAAAAA
题目名称	[NOI 2011]道路修建	最终得分	100
用户昵称	天一阁	是否通过	通过
代码语言	C++	运行时间	7.106 s
提交时间	2015-06-24 09:09:11	内存使用	81.83 MiB

#include <cstdio>
#include <cstring>
#include <algorithm>
#include <queue>

#define N 2000010
#define p E[i].x
#define LL long long

using namespace std;

struct edge{
	int x,to,v;
}E[N<<1];

int totE,n;
int g[N],siz[N],fa[N],dfsn[N],len[N];
bool v[N];
queue<int> q;

int Abs(int x){
	if(x<0) return -x;
	return x;
}

void ade(int x,int y,int v){
	E[++totE]=(edge){y,g[x],v}; g[x]=totE;
}

int main(){
	freopen("noi2011_road.in","r",stdin);
	freopen("noi2011_road.out","w",stdout);
	scanf("%d",&n);
	for(int i=1,x,y;i<n;i++){
		int v;
		scanf("%d%d%d",&x,&y,&v);
		ade(x,y,v);
		ade(y,x,v);
	}
	memset(v,0,sizeof(v));
	q.push(1); v[1]=1;
	while(!q.empty()){
		int x=q.front(); q.pop();
		dfsn[++dfsn[0]]=x;
		for(int i=g[x];i;i=E[i].to)
			if(!v[p]){
				len[p]=E[i].v;
				v[p]=1; fa[p]=x;
				q.push(p);
			}
	}
	for(int t=n;t>=1;t--){
		int x=dfsn[t];
		siz[x]++;
		if(fa[x]) siz[fa[x]]+=siz[x];
	}
	LL ans=0;
	for(int i=2;i<=n;i++) ans+=Abs(siz[1]-2*siz[i])*(LL)len[i];
	printf("%lld\n",ans);
	return 0;
}
/*
10
7 8 799682
9 4 530707
6 1 505653
3 6 195384
2 1 546856
10 4 975721
4 7 501601
8 3 973476
5 3 300345
*/