记录编号	151791	评测结果	AAAAAAAAAAAAAAAAAAAA
题目名称	[NOI 2011]道路修建	最终得分	100
用户昵称	HouJikan	是否通过	通过
代码语言	C++	运行时间	7.719 s
提交时间	2015-03-10 20:59:42	内存使用	27.02 MiB

#include <iostream>
#include <cstring>
#include <string>
#include <cstdio>
#include <cstdlib>
#include <cmath>
#include <algorithm>
#include <queue>
#include <stack>
#include <map>
#include <set>
#include <list>
#include <vector>
#include <ctime>
#include <functional>
#define pritnf printf
#define scafn scanf
#define sacnf scanf
#define For(i,j,k) for(int i=(j);i<=(k);(i)++)
#define Clear(a) memset(a,0,sizeof(a))
using namespace std;
typedef unsigned int Uint;
const int INF=0x3fffffff;
///==============struct declaration==============
struct adj{
   int to,dist;
   adj(int to=0,int dist=0):to(to),dist(dist){}
};
///==============var declaration=================
const int MAXN=1000050;
long long ans=0;
int n;
int cur[MAXN],siz[MAXN],pa[MAXN],size[MAXN];
vector <adj> Edge[MAXN];
///==============function declaration============
inline long long _abs(long long a){return a<0?-a:a;}
///==============main code=======================
int main()
{

   freopen("noi2011_road.in","r",stdin);
   freopen("noi2011_road.out","w",stdout);

   scanf("%d",&n);
   for(int i=1;i<n;i++){
      int s,e,d;scanf("%d%d%d",&s,&e,&d);
      Edge[s].push_back(adj(e,d));Edge[e].push_back(adj(s,d));
   }
   for(int i=1;i<=n;i++) size[i]=Edge[i].size();
   memset(siz,-1,sizeof(siz));memset(cur,-1,sizeof(cur));
   int x=1;pa[1]=1;
   while (cur[1]<size[1]||x!=1){
      if (cur[x]!=-1&&Edge[x][cur[x]].to!=pa[x]){
         siz[x]+=siz[Edge[x][cur[x]].to];
         ans+=_abs((long long)n-siz[Edge[x][cur[x]].to]*2)*Edge[x][cur[x]].dist;
      }
      if (++cur[x]==0)  siz[x]=1;
      if (cur[x]==size[x]){x=pa[x];continue;}
      if (Edge[x][cur[x]].to==pa[x])   continue;
      pa[Edge[x][cur[x]].to]=x;x=Edge[x][cur[x]].to;
   }
   printf("%lld\n",ans);
   return 0;
}
///================fuction code====================