记录编号	60298	评测结果	AAAAAAAAAAAAAAAAAAAA
题目名称	[NOI 2011]道路修建	最终得分	100
用户昵称	cstdio	是否通过	通过
代码语言	C++	运行时间	6.878 s
提交时间	2013-05-21 21:09:21	内存使用	24.25 MiB

#include <cstdio>
#include <iostream>
#include <cstdlib>
#include <cstring>
#define F_I "noi2011_road.in"
#define F_O "noi2011_road.out"
using namespace std;
typedef long long ll;
const ll Nx=1000010;
ll N,f[Nx],Ans,Pr[Nx],W[Nx];
class Node{
public:
	ll n,w;
	Node *pr;
}*Adj[Nx];
class Queue{
public:
	ll h,t,li[Nx];
	void bfs(){
		h=t=1;
		li[t++]=1;
		while(h<t){
		ll H=li[h++];
			f[H]=1;
			for(Node *p=Adj[H];p;p=p->pr)
				if(f[p->n]==0){
					li[t++]=p->n;
					Pr[p->n]=H;
					W[p->n]=p->w;
				}
		}
		while(--t)
			f[Pr[li[t]]]+=f[li[t]];
	}
}Q;
void add(int u,int v,int w){
Node *p=new Node;
	p->n=v,p->w=w;
	p->pr=Adj[u];
	Adj[u]=p;
}
void init(){
ll i,u,v,w;
	scanf("%lld",&N);
	memset(Adj,0,sizeof(Adj));
	for(i=1;i<N;i++){
		scanf("%lld%lld%lld",&u,&v,&w);
		add(u,v,w);
		add(v,u,w);
	}
}
int main(){
freopen(F_I,"r",stdin);
freopen(F_O,"w",stdout);
	init();
	
	Q.bfs();
	
	for(int i=2;i<=N;i++)
		Ans+=W[i]*abs(N-f[i]-f[i]);
	cout<<Ans<<endl;
	
	return 0;
}