BZOJ1827[USACO 2010 Mar Gold 1.Great Cow Gathering]——树的遍历

 1 #include<queue>
 2 #include<cmath>
 3 #include<cstdio>
 4 #include<cstring>
 5 #include<iostream>
 6 #include<algorithm>
 7 using namespace std;
 8 long long size[100010];
 9 int head[100010];
10 int next[200010];
11 int to[200010];
12 long long val[200010];
13 int f[100010];
14 long long s[100010];
15 long long a[100010];
16 int x,y;
17 long long v;
18 int n;
19 int tot;
20 long long sum;
21 long long ans;
22 void add(int x,int y,long long v)
23 {
24     tot++;
25     next[tot]=head[x];
26     head[x]=tot;
27     to[tot]=y;
28     val[tot]=v;
29 }
30 void dfs(int x,int fa)
31 {
32     f[x]=fa;
33     for(int i=head[x];i;i=next[i])
34     {
35         if(to[i]!=fa)
36         {
37             dfs(to[i],x);
38             size[x]+=size[to[i]];
39         }
40     }
41 }
42 void dfs2(int x,long long dep)
43 {
44     ans+=dep*a[x];
45     for(int i=head[x];i;i=next[i])
46     {
47         if(to[i]!=f[x])
48         {
49             dfs2(to[i],dep+val[i]);
50         }
51     }
52 }
53 void find(int x)
54 {
55     for(int i=head[x];i;i=next[i])
56     {
57         if(to[i]!=f[x])
58         {
59             s[to[i]]=s[x]-size[to[i]]*val[i]+(sum-size[to[i]])*val[i];
60             find(to[i]);
61         }
62     }
63 }
64 int main()
65 {
66     scanf("%d",&n);
67     for(int i=1;i<=n;i++)
68     {
69         scanf("%lld",&size[i]);
70         a[i]=size[i];
71         sum+=size[i];
72     }
73     for(int i=1;i<n;i++)
74     {
75         scanf("%d%d%lld",&x,&y,&v);
76         add(x,y,v);
77         add(y,x,v);
78     }
79     dfs(1,1);
80     dfs2(1,0ll);
81     s[1]=ans;
82     find(1);
83     ans=1ll<<62;
84     for(int i=1;i<=n;i++)
85     {
86         ans=min(ans,s[i]);
87     }
88     printf("%lld",ans);
89 }