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

#include<cstdio>
#include<cstring>
#include<algorithm>
using namespace std;
const int maxn=1000010;
namespace mine{
//#define NEGATE_NEEDED
    template<class T>inline void readint(T &__x){
        static int __c;
#ifdef NEGATE_NEEDED
        static bool __neg;
#endif
        __x=0;
#ifdef NEGATE_NEEDED
        __neg=false;
#endif
        do __c=getchar();while(__c==' '||__c=='\n'||__c=='\r'||__c=='\t');
#ifdef NEGATE_NEEDED
        if(__c=='-'){
            __neg=true;
            __c=getchar();
        }
#endif
        for(;__c>='0'&&__c<='9';__c=getchar())__x=__x*10+(__c^48);
#ifdef NEGATE_NEEDED
        if(__neg)__x=-__x;
#endif
    }
    template<class T>inline void writeint(T __x){
        static int __a[40],__i,__j;
#ifdef NEGATE_NEEDED
        static bool __neg;
        __neg=__x<0;
        if(__neg)__x=-__x;
#endif
        __i=0;
        do{
            __a[__i++]=__x%10^48;
            __x/=10;
        }while(__x);
#ifdef NEGATE_NEEDED
        if(__neg)putchar('-');
#endif
        for(__j=__i-1;__j^-1;__j--)putchar(__a[__j]);
    }
}
using namespace mine;
struct edge{int to,prev,w;}e[maxn<<1];
void addedge(int,int,int);
void bfs();
int n,last[maxn],len=0,prt[maxn],size[maxn],q[maxn],head,tail,x,y,z;
long long ans=0ll;
int main(){
#define MINE
#ifdef MINE
	freopen("noi2011_road.in","r",stdin);
	freopen("noi2011_road.out","w",stdout);
#endif
	readint(n);
	for(int i=1;i<n;i++){
		readint(x);
		readint(y);
		readint(z);
		addedge(x,y,z);
		addedge(y,x,z);
	}
	bfs();
	writeint(ans);
#ifndef MINE
	printf("\n-------------------------DONE-------------------------\n");
	for(;;);
#else
	fclose(stdin);
	fclose(stdout);
#endif
	return 0;
}
inline void addedge(int x,int y,int z){
	e[++len].to=y;
	e[len].w=z;
	e[len].prev=last[x];
	last[x]=len;
}
void bfs(){
	int x;
	head=tail=1;
	q[tail++]=1;
	while(head!=tail){
		x=q[head++];
		size[x]=1;
		for(int i=last[x];i;i=e[i].prev)if(e[i].to!=prt[x]){
			prt[e[i].to]=x;
			q[tail++]=e[i].to;
		}
	}
	for(int i=n;i;i--){
		size[prt[q[i]]]+=size[q[i]];
	}
	for(int k=1;k<=n;k++)
		for(int i=last[q[k]];i;i=e[i].prev)if(e[i].to!=prt[q[k]])ans+=e[i].w*(long long)abs(n-(size[e[i].to]<<1));
}
/*
6
1 2 1
1 3 1
1 4 2
6 3 1
5 2 1
Answer:
20
*/