#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef pair<ll,ll> ii;
int p[100010];
int mx[100010];
int val[100010];
vector<ii> v;
bool comp(ii a,ii b){
ll x=max(val[a.first],val[a.second]);
ll y=max(val[b.first],val[b.second]);
return x<y;
}
int findset(int x){
if(x==p[x])return x;
return p[x]=findset(p[x]);
}
ll ans=0;
void unionset(int i,int j){
i=findset(i);
j=findset(j);
if(i!=j){
ans+=mx[i]+mx[j];
mx[j]=max(mx[i],mx[j]);
p[i]=j;
}
}
int main(){
int n;
cin>>n;
for(int i=1;i<=n;i++){
cin>>val[i];
mx[i]=val[i];
p[i]=i;
}
int a,b;
for(int i=1;i<n;i++){
cin>>a>>b;
v.push_back(ii(a,b));
}
sort(v.begin(),v.end(),comp);
for(int i=0;i<n-1;i++){
unionset(v[i].first,v[i].second);
}
cout<<ans<<endl;
}
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
1 ms |
364 KB |
Output is correct |
2 |
Correct |
0 ms |
364 KB |
Output is correct |
3 |
Correct |
0 ms |
364 KB |
Output is correct |
4 |
Correct |
0 ms |
364 KB |
Output is correct |
5 |
Correct |
1 ms |
384 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
94 ms |
3444 KB |
Output is correct |
2 |
Correct |
72 ms |
2148 KB |
Output is correct |
3 |
Correct |
70 ms |
2148 KB |
Output is correct |
4 |
Correct |
78 ms |
3296 KB |
Output is correct |
5 |
Correct |
119 ms |
3700 KB |
Output is correct |
6 |
Correct |
124 ms |
4700 KB |
Output is correct |
7 |
Correct |
106 ms |
3676 KB |
Output is correct |
8 |
Correct |
99 ms |
3676 KB |
Output is correct |
9 |
Correct |
64 ms |
2676 KB |
Output is correct |
10 |
Correct |
121 ms |
4360 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
1 ms |
364 KB |
Output is correct |
2 |
Correct |
0 ms |
364 KB |
Output is correct |
3 |
Correct |
0 ms |
364 KB |
Output is correct |
4 |
Correct |
0 ms |
364 KB |
Output is correct |
5 |
Correct |
1 ms |
384 KB |
Output is correct |
6 |
Correct |
1 ms |
364 KB |
Output is correct |
7 |
Correct |
1 ms |
364 KB |
Output is correct |
8 |
Correct |
1 ms |
364 KB |
Output is correct |
9 |
Correct |
2 ms |
364 KB |
Output is correct |
10 |
Correct |
2 ms |
364 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
1 ms |
364 KB |
Output is correct |
2 |
Correct |
0 ms |
364 KB |
Output is correct |
3 |
Correct |
0 ms |
364 KB |
Output is correct |
4 |
Correct |
0 ms |
364 KB |
Output is correct |
5 |
Correct |
1 ms |
384 KB |
Output is correct |
6 |
Correct |
94 ms |
3444 KB |
Output is correct |
7 |
Correct |
72 ms |
2148 KB |
Output is correct |
8 |
Correct |
70 ms |
2148 KB |
Output is correct |
9 |
Correct |
78 ms |
3296 KB |
Output is correct |
10 |
Correct |
119 ms |
3700 KB |
Output is correct |
11 |
Correct |
124 ms |
4700 KB |
Output is correct |
12 |
Correct |
106 ms |
3676 KB |
Output is correct |
13 |
Correct |
99 ms |
3676 KB |
Output is correct |
14 |
Correct |
64 ms |
2676 KB |
Output is correct |
15 |
Correct |
121 ms |
4360 KB |
Output is correct |
16 |
Correct |
1 ms |
364 KB |
Output is correct |
17 |
Correct |
1 ms |
364 KB |
Output is correct |
18 |
Correct |
1 ms |
364 KB |
Output is correct |
19 |
Correct |
2 ms |
364 KB |
Output is correct |
20 |
Correct |
2 ms |
364 KB |
Output is correct |
21 |
Correct |
27 ms |
1256 KB |
Output is correct |
22 |
Correct |
24 ms |
1256 KB |
Output is correct |
23 |
Correct |
117 ms |
3680 KB |
Output is correct |
24 |
Correct |
81 ms |
3296 KB |
Output is correct |
25 |
Correct |
81 ms |
3424 KB |
Output is correct |
26 |
Correct |
53 ms |
2020 KB |
Output is correct |
27 |
Correct |
62 ms |
2148 KB |
Output is correct |
28 |
Correct |
73 ms |
3424 KB |
Output is correct |
29 |
Correct |
49 ms |
2020 KB |
Output is correct |
30 |
Correct |
121 ms |
3680 KB |
Output is correct |