#include<bits/stdc++.h>
#define ll long long
#define f first
#define s second
#define pb push_back
using namespace std;
ll n,p[200005],mx[200005],ans;
pair<ll,ll>a[200005];
vector<ll>v[200005];
ll find(ll x){
if(x == p[x])return x;
return p[x] = find(p[x]);
}
void join(ll x,ll y){
x = find(x);
y = find(y);
if(x == y)return;
ans += mx[x] + mx[y];
mx[x] = max(mx[x] , mx[y]);
p[y] = x;
}
int main(){
ios::sync_with_stdio(false);
cin >> n;
for(int i=1; i<=n; i++){
p[i] = i;
cin >> a[i].f;
mx[i] = a[i].f;
a[i].s = i;
}
for(int i=1; i<n; i++){
ll x,y;
cin >> x >> y;
if(a[x].f >= a[y].f)
v[x].pb(y);
if(a[y].f >= a[x].f)
v[y].pb(x);
}
sort(a + 1 , a + n + 1);
for(int o=1; o<=n; o++){
ll x = a[o].s;
for(int i=0; i<v[x].size(); i++){
ll y = v[x][i];
join(x , y);
}
}
cout << ans << '\n';
return 0;
}
Compilation message
sjekira.cpp: In function 'int main()':
sjekira.cpp:42:23: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<long long int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
42 | for(int i=0; i<v[x].size(); i++){
| ~^~~~~~~~~~~~
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
4 ms |
5100 KB |
Output is correct |
2 |
Correct |
5 ms |
5100 KB |
Output is correct |
3 |
Correct |
5 ms |
5100 KB |
Output is correct |
4 |
Correct |
4 ms |
5100 KB |
Output is correct |
5 |
Correct |
5 ms |
5100 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
56 ms |
10988 KB |
Output is correct |
2 |
Correct |
41 ms |
9580 KB |
Output is correct |
3 |
Correct |
40 ms |
9452 KB |
Output is correct |
4 |
Correct |
44 ms |
9964 KB |
Output is correct |
5 |
Correct |
66 ms |
12396 KB |
Output is correct |
6 |
Correct |
57 ms |
14956 KB |
Output is correct |
7 |
Correct |
40 ms |
13164 KB |
Output is correct |
8 |
Correct |
37 ms |
12652 KB |
Output is correct |
9 |
Correct |
25 ms |
10220 KB |
Output is correct |
10 |
Correct |
46 ms |
14572 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
4 ms |
5100 KB |
Output is correct |
2 |
Correct |
5 ms |
5100 KB |
Output is correct |
3 |
Correct |
5 ms |
5100 KB |
Output is correct |
4 |
Correct |
4 ms |
5100 KB |
Output is correct |
5 |
Correct |
5 ms |
5100 KB |
Output is correct |
6 |
Correct |
4 ms |
5100 KB |
Output is correct |
7 |
Correct |
5 ms |
5100 KB |
Output is correct |
8 |
Correct |
4 ms |
5100 KB |
Output is correct |
9 |
Correct |
4 ms |
5100 KB |
Output is correct |
10 |
Correct |
5 ms |
5104 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
4 ms |
5100 KB |
Output is correct |
2 |
Correct |
5 ms |
5100 KB |
Output is correct |
3 |
Correct |
5 ms |
5100 KB |
Output is correct |
4 |
Correct |
4 ms |
5100 KB |
Output is correct |
5 |
Correct |
5 ms |
5100 KB |
Output is correct |
6 |
Correct |
56 ms |
10988 KB |
Output is correct |
7 |
Correct |
41 ms |
9580 KB |
Output is correct |
8 |
Correct |
40 ms |
9452 KB |
Output is correct |
9 |
Correct |
44 ms |
9964 KB |
Output is correct |
10 |
Correct |
66 ms |
12396 KB |
Output is correct |
11 |
Correct |
57 ms |
14956 KB |
Output is correct |
12 |
Correct |
40 ms |
13164 KB |
Output is correct |
13 |
Correct |
37 ms |
12652 KB |
Output is correct |
14 |
Correct |
25 ms |
10220 KB |
Output is correct |
15 |
Correct |
46 ms |
14572 KB |
Output is correct |
16 |
Correct |
4 ms |
5100 KB |
Output is correct |
17 |
Correct |
5 ms |
5100 KB |
Output is correct |
18 |
Correct |
4 ms |
5100 KB |
Output is correct |
19 |
Correct |
4 ms |
5100 KB |
Output is correct |
20 |
Correct |
5 ms |
5104 KB |
Output is correct |
21 |
Correct |
17 ms |
6764 KB |
Output is correct |
22 |
Correct |
16 ms |
6508 KB |
Output is correct |
23 |
Correct |
74 ms |
11984 KB |
Output is correct |
24 |
Correct |
46 ms |
10092 KB |
Output is correct |
25 |
Correct |
48 ms |
9964 KB |
Output is correct |
26 |
Correct |
38 ms |
8428 KB |
Output is correct |
27 |
Correct |
38 ms |
8940 KB |
Output is correct |
28 |
Correct |
59 ms |
9984 KB |
Output is correct |
29 |
Correct |
68 ms |
8576 KB |
Output is correct |
30 |
Correct |
84 ms |
12524 KB |
Output is correct |