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
| #include<bits/stdc++.h> #define N 1000010 #define abs(a) ((a)>0?(a):(-(a))) #define mem(a,b) memset(a,b,sizeof(a)) #define ll long long #define fsb(a,b,c) for(ll a=b;a<=c;a++) #define fbs(a,b,c) for(ll a=b;a>=c;a--) using namespace std; struct edge{ ll p,nt,mark; }a[N*2]; struct node{ ll x,y,z; }b[N]; ll n,cnt=0,head[N],x,y,z,ans=0,f[N]; template<typename qw>inline void rll(qw &x){ x=0;qw f=1;char c=getchar(); while(!isdigit(c))f=c=='-'?-1:f,c=getchar(); while(isdigit(c))x=x*10+c-'0',c=getchar(); x*=f; } inline void add(ll x,ll y,ll z){ a[++cnt].p=y;a[cnt].nt=head[x];head[x]=cnt;a[cnt].mark=z; } inline void dfs(ll u,ll fa){ f[u]=1; for(ll t=head[u];t!=-1;t=a[t].nt){ ll v=a[t].p;if(v==fa)continue; dfs(v,u);f[u]+=f[v];ans+=abs(n-2*f[v])*b[a[t].mark].z; } } int main(){ rll(n);mem(head,255); fsb(i,1,n-1){ rll(x);rll(y);rll(z);add(x,y,i);add(y,x,i); b[i]=(node){x,y,z}; } mem(f,0);dfs(1,0); printf("%lld\n",ans); return 0; }
|