#ifndef Local
#pragma GCC optimize("O3,unroll-loops")
#pragma GCC target("avx2,bmi,bmi2,lzcnt,popcnt")
#endif
#include <bits/stdc++.h>
#define int long long
#define pb push_back
#define lim 100005
using namespace std;
const int mod=1000000007ll;
int parent[lim];
int maxi[lim];
int find(int i){
if(parent[i]==i){
return i;
}
return parent[i]=find(parent[i]);
}
int fm(int i){
return maxi[find(i)];
}
void unite(int i,int j){
int x=find(i),y=find(j);
if(x!=y){
maxi[y]=maxi[x]=max(maxi[x],maxi[y]);
parent[y]=x;
}
}
vector<int>v[lim];
void solve(){
int n;
cin>>n;
int h[n];
for(int i=0;i<n;i++){
cin>>h[i];
}
for(int i=0;i<n-1;i++){
int x,y;
cin>>x>>y;
x--,y--;
v[x].pb(y);
v[y].pb(x);
}
for(int i=0;i<n;i++){
parent[i]=i;
maxi[i]=h[i];
}
int a[n];
for(int i=0;i<n;i++)a[i]=i;
sort(a,a+n,[&](int i,int j)->bool {
return h[i]<h[j];
});
for(int i=0;i<n;i++){
sort(v[i].begin(),v[i].end(),[&](int i,int j)->bool {
return h[i]<h[j];
});
}
int ans=0;
bool past[n];
memset(past,0,n);
for(int i=0;i<n;i++){
past[a[i]]=1;
for(int j:v[a[i]]){
if(past[j]){
ans+=fm(a[i])+fm(j);
unite(a[i],j);
}
}
}
cout<<ans<<"\n";
}
signed main(){
ios_base::sync_with_stdio(false);
cin.tie(NULL);cout.tie(NULL);
#ifdef Local
freopen("in","r",stdin);
freopen("out","w",stdout);
#endif
int t=1;
//cin>>t;
while (t--)
{
solve();
}
}
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
1 ms |
2652 KB |
Output is correct |
2 |
Correct |
1 ms |
2652 KB |
Output is correct |
3 |
Correct |
1 ms |
2652 KB |
Output is correct |
4 |
Correct |
1 ms |
2652 KB |
Output is correct |
5 |
Correct |
1 ms |
2652 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
32 ms |
7900 KB |
Output is correct |
2 |
Correct |
24 ms |
6536 KB |
Output is correct |
3 |
Correct |
23 ms |
6552 KB |
Output is correct |
4 |
Correct |
26 ms |
7284 KB |
Output is correct |
5 |
Correct |
39 ms |
9048 KB |
Output is correct |
6 |
Correct |
33 ms |
9552 KB |
Output is correct |
7 |
Correct |
29 ms |
8584 KB |
Output is correct |
8 |
Correct |
24 ms |
8028 KB |
Output is correct |
9 |
Correct |
16 ms |
6236 KB |
Output is correct |
10 |
Correct |
29 ms |
9384 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
1 ms |
2652 KB |
Output is correct |
2 |
Correct |
1 ms |
2652 KB |
Output is correct |
3 |
Correct |
1 ms |
2652 KB |
Output is correct |
4 |
Correct |
1 ms |
2652 KB |
Output is correct |
5 |
Correct |
1 ms |
2652 KB |
Output is correct |
6 |
Correct |
1 ms |
2652 KB |
Output is correct |
7 |
Correct |
1 ms |
2652 KB |
Output is correct |
8 |
Correct |
1 ms |
2652 KB |
Output is correct |
9 |
Correct |
1 ms |
2652 KB |
Output is correct |
10 |
Correct |
2 ms |
2652 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
1 ms |
2652 KB |
Output is correct |
2 |
Correct |
1 ms |
2652 KB |
Output is correct |
3 |
Correct |
1 ms |
2652 KB |
Output is correct |
4 |
Correct |
1 ms |
2652 KB |
Output is correct |
5 |
Correct |
1 ms |
2652 KB |
Output is correct |
6 |
Correct |
32 ms |
7900 KB |
Output is correct |
7 |
Correct |
24 ms |
6536 KB |
Output is correct |
8 |
Correct |
23 ms |
6552 KB |
Output is correct |
9 |
Correct |
26 ms |
7284 KB |
Output is correct |
10 |
Correct |
39 ms |
9048 KB |
Output is correct |
11 |
Correct |
33 ms |
9552 KB |
Output is correct |
12 |
Correct |
29 ms |
8584 KB |
Output is correct |
13 |
Correct |
24 ms |
8028 KB |
Output is correct |
14 |
Correct |
16 ms |
6236 KB |
Output is correct |
15 |
Correct |
29 ms |
9384 KB |
Output is correct |
16 |
Correct |
1 ms |
2652 KB |
Output is correct |
17 |
Correct |
1 ms |
2652 KB |
Output is correct |
18 |
Correct |
1 ms |
2652 KB |
Output is correct |
19 |
Correct |
1 ms |
2652 KB |
Output is correct |
20 |
Correct |
2 ms |
2652 KB |
Output is correct |
21 |
Correct |
10 ms |
4444 KB |
Output is correct |
22 |
Correct |
9 ms |
4048 KB |
Output is correct |
23 |
Correct |
42 ms |
9296 KB |
Output is correct |
24 |
Correct |
30 ms |
7516 KB |
Output is correct |
25 |
Correct |
29 ms |
7260 KB |
Output is correct |
26 |
Correct |
19 ms |
5888 KB |
Output is correct |
27 |
Correct |
23 ms |
6492 KB |
Output is correct |
28 |
Correct |
40 ms |
7664 KB |
Output is correct |
29 |
Correct |
22 ms |
6740 KB |
Output is correct |
30 |
Correct |
45 ms |
11784 KB |
Output is correct |