记录编号	593834	评测结果	AAAAAAAAAAAAAAAAAAAA
题目名称	[NOI 2011]道路修建	最终得分	100
用户昵称	健康铀	是否通过	通过
代码语言	C++	运行时间	6.916 s
提交时间	2024-09-17 15:53:52	内存使用	33.97 MiB

#include<bits/stdc++.h>
using namespace std;
long long n,s[1000010],top,cnt,he[1000010],d[1000010],ans;
struct node{
	long long v;
	long long nx;
	long long z;
}e[2000010];
void add(long long x,long long y,long long z){
	e[++cnt].v=y,e[cnt].nx=he[x],e[cnt].z=z,he[x]=cnt;
}
void get(long long x,long long fa,long long r){
	s[x]=1;
	for(long long i=he[x];i;i=e[i].nx){
		long long v=e[i].v;
		if(v==fa){
			continue;
		}
		get(v,x,e[i].z);
		s[x]+=s[v];
	}
	ans+=abs(2*s[x]-n)*r;
} 
int main(){
	freopen("noi2011_road.in","r",stdin);
	freopen("noi2011_road.out","w",stdout);
	cin>>n;
	for(long long i=1;i<=n-1;i++){
		long long x,y,z;
		cin>>x>>y>>z;
		add(x,y,z);
		add(y,x,z);
	}
	get(1,0,0);
	cout<<ans;
	return 0;
}