一开始看到题还以为是傻逼并查集
原来是傻逼bfs
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 |
// <2435.cpp> - 07/28/16 19:37:58 // This file is created by XuYike's black technology automatically. // Copyright (C) 2015 ChangJun High School, Inc. // I don't know what this program is. #include <iostream> #include <vector> #include <queue> #include <algorithm> #include <cstring> #include <cstdio> #include <cmath> using namespace std; typedef long long lol; int gi(){ int res=0,fh=1;char ch=getchar(); while((ch>'9'||ch<'0')&&ch!='-')ch=getchar(); if(ch=='-')fh=-1,ch=getchar(); while(ch>='0'&&ch<='9')res=res*10+ch-'0',ch=getchar(); return fh*res; } const int MAXN=1000010; const int INF=1e9; int bt=1,b[MAXN],next[MAXN<<1],to[MAXN<<1],val[MAXN<<1]; inline void add(int x,int y,int z){ next[++bt]=b[x];b[x]=bt;to[bt]=y;val[bt]=z; next[++bt]=b[y];b[y]=bt;to[bt]=x;val[bt]=z; } queue <int> q; bool vis[MAXN]; int tot,dfn[MAXN],size[MAXN],f[MAXN]; int main(){ int n=gi(); for(int i=1;i<n;i++){ int a=gi(),b=gi(),c=gi(); add(a,b,c); } q.push(1); while(!q.empty()){ int now=q.front();q.pop(); vis[now]=1; dfn[++tot]=now; for(int i=b[now];i;i=next[i]){ if(vis[to[i]])continue; f[to[i]]=i^1; q.push(to[i]); } } lol ans=0; for(int i=n;i;i--){ int now=dfn[i]; size[now]++; ans+=1ll*abs(n-2*size[now])*val[f[now]]; size[to[f[now]]]+=size[now]; } printf("%lld",ans); return 0; } |