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
59
60
61
62
63
64
65
66
67
68
69
| #include <iostream>
#include <vector>
#include <bitset>
#define ll long long
using namespace std;
const int maxn = static_cast<int>(1e5) + 7;
const long long MAXSON=1e18+7;
int n,a,b,l,core;
int c[maxn];
long long maxSonTree[maxn],minSon=MAXSON;
bitset</*100007*/ maxn> vis;
vector<pair<int,int> > g[maxn];
long long ans,sumN;
long long dfs(ll x,ll dis) {
long long accSon=0,maxSon=0,treeSon;
for(int i=0;i<g[x].size();i++) {
ll son=g[x][i].first,len=g[x][i].second;
if(!vis[son]) {
vis[son]=true;
treeSon=dfs(son,dis+len);
accSon+=treeSon;
maxSon=max(maxSon,treeSon);
}
}
maxSon = max(maxSon,sumN-accSon-c[x]);
maxSonTree[x]=maxSon;
return accSon+c[x];
}
void dfs2(ll x,ll dis) {
ans+=(c[x]*dis);
for(int i=0;i<g[x].size();i++) {
ll son=g[x][i].first,len=g[x][i].second;
if(!vis[son]) {
vis[son]=true;
dfs2(son,dis+len);
}
}
}
int main()
{
cin>>n;
for(int i=1;i<=n;i++) {
cin>>c[i];
sumN+=c[i];
}
for(int i=1;i<=n-1;i++) {
cin>>a>>b>>l;
g[a].push_back(make_pair(b,l));
g[b].push_back(make_pair(a,l));
}
vis[1]=true;
dfs(1,0);
for(int i=1;i<=n;i++) {
if(maxSonTree[i]<minSon)
core=i,minSon=maxSonTree[i];
}
vis.reset(),ans=0;
vis[core]=true;
dfs2(core,0);
cout<<ans<<endl;
return 0;
}
|
