记录编号	338994	评测结果	AAAAAAAAAAAAAAAAAAAA
题目名称	[NOI 2011]道路修建	最终得分	100
用户昵称	_Itachi	是否通过	通过
代码语言	C++	运行时间	9.136 s
提交时间	2016-11-05 17:20:31	内存使用	30.75 MiB

#include<cstdio>
#include<cstring>
#include<algorithm>
using namespace std;
const int maxn=1000005;
#define LL long long
int n,len=1,size[maxn],head[maxn],st[maxn],cnt=0,fa[maxn];
struct Rabit_tree{int to,next,dis;}e[maxn<<1];
void Rabit_set(int prt,int son,int dis){
	e[++len].to=son,e[len].next=head[prt],head[prt]=len,e[len].dis=dis;	
}
#define to e[i].to
int Rabit_abs(int x){return x<0?-x:x;}
LL Rabit_run(){
	int RT=n>>1|1,rt,i;LL ans=0;st[++cnt]=RT;
	while(cnt){
		rt=st[cnt];
		if(!size[rt]){
			size[rt]=1;
			for(i=head[rt];i;i=e[i].next)
				if(fa[rt]^to)fa[to]=rt,st[++cnt]=to;
		}
		else{
			for(i=head[rt];i;i=e[i].next)
				if(fa[to]==rt)
					ans+=Rabit_abs(n-size[to]-size[to])*1ll*e[i].dis;
			size[fa[rt]]+=size[rt];	
			cnt--;
		}
	}
	return ans;
}
void Rabit_main(){
	scanf("%d",&n);int i,x,y,z;
	for(i=1;i<n;i++)
		scanf("%d%d%d",&x,&y,&z),Rabit_set(x,y,z),Rabit_set(y,x,z);
	printf("%lld\n",Rabit_run());
}
int main(){
#define _Rabit _RABIT
#ifdef _Rabit
	freopen("noi2011_road.in","r",stdin);
	freopen("noi2011_road.out","w",stdout);
#endif
	Rabit_main();
#ifndef _Rabit
	getchar(),getchar();
#endif
	fclose(stdin);fclose(stdout);
	return 0;
}