#include <bits/stdc++.h>
#define fi first
#define se second
#define pb push_back
#define sz(a) (int)a.size()
#define all(a) a.begin(),a.end()
#define rep(i,n) for(int i=0;i<n;i++)
#define crep(i,x,n) for(int i=x;i<n;i++)
#define drep(i,n) for(int i=n-1;i>=0;i--)
#define vec(...) vector<__VA_ARGS__>
#define _3HaBFkZ ios_base::sync_with_stdio(false),cin.tie(0),cout.tie(0)
using namespace std;
typedef long long ll;
typedef long double ld;
using pii=pair<int,int>;
using vi=vector<int>;
struct dsu{
int n,size_;
vector<int> par,siz,maxima;
dsu(int m,vi a){
init(m,a);
}
void init(int m,vi a){
n=m;
size_=m;
par.resize(n,0);
siz.resize(n,0);
maxima.resize(n,0);
for(int i=0;i<n;i++){
par[i]=i;
siz[i]=1;
maxima[i]=a[i];
}
}
void merge(int x,int y,int type=0){
int a=parent(x),b=parent(y);
if(a==b) return;
size_--;
if(siz[a]>siz[b]) {
siz[a]+=siz[b];
par[b]=a;
maxima[a]=max(maxima[a],maxima[b]);
}else{
siz[b]+=siz[a];
par[a]=b;
maxima[b]=max(maxima[b],maxima[a]);
}
}
int parent(int x){
return par[x]==x?x:parent(par[x]);
}
bool same(int x, int y){
return parent(x)==parent(y);
}
int size(){
return size_;
}
};
int main(){
_3HaBFkZ;
int n;
cin>>n;
vi a(n);
rep(i,n){
cin>>a[i];
}
vec(set<int>) adj(n);
rep(i,n-1){
int u,v;
cin>>u>>v;
u--,v--;
adj[u].insert(v);
adj[v].insert(u);
}
vec(pii) rbts;
rep(i,n){
rbts.pb({a[i],i});
}
sort(all(rbts));
reverse(all(rbts));
vec(pii) prcs;
rep(i,sz(rbts)){
int v=rbts[i].se;
ll val=rbts[i].fi;
for(auto u : adj[v]){
prcs.pb({v,u});
adj[u].erase(v);
}
}
reverse(all(prcs));
dsu uf(n,a);
ll ans=0;
rep(i,sz(prcs)){
int v=prcs[i].fi,u=prcs[i].se;
int par1=uf.parent(v),par2=uf.parent(u);
ans+=uf.maxima[par1];
ans+=uf.maxima[par2];
uf.merge(u,v);
}
cout<<ans<<"\n";
//
return 0;
}
Compilation message
sjekira.cpp: In function 'int main()':
sjekira.cpp:86:6: warning: unused variable 'val' [-Wunused-variable]
86 | ll val=rbts[i].fi;
| ^~~
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
1 ms |
204 KB |
Output is correct |
2 |
Correct |
0 ms |
204 KB |
Output is correct |
3 |
Correct |
0 ms |
204 KB |
Output is correct |
4 |
Correct |
0 ms |
204 KB |
Output is correct |
5 |
Correct |
0 ms |
204 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
59 ms |
14964 KB |
Output is correct |
2 |
Correct |
44 ms |
11368 KB |
Output is correct |
3 |
Correct |
42 ms |
11052 KB |
Output is correct |
4 |
Correct |
46 ms |
12296 KB |
Output is correct |
5 |
Correct |
76 ms |
18268 KB |
Output is correct |
6 |
Correct |
52 ms |
18260 KB |
Output is correct |
7 |
Correct |
40 ms |
17664 KB |
Output is correct |
8 |
Correct |
37 ms |
16052 KB |
Output is correct |
9 |
Correct |
23 ms |
10560 KB |
Output is correct |
10 |
Correct |
45 ms |
20440 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
1 ms |
204 KB |
Output is correct |
2 |
Correct |
0 ms |
204 KB |
Output is correct |
3 |
Correct |
0 ms |
204 KB |
Output is correct |
4 |
Correct |
0 ms |
204 KB |
Output is correct |
5 |
Correct |
0 ms |
204 KB |
Output is correct |
6 |
Correct |
1 ms |
460 KB |
Output is correct |
7 |
Correct |
1 ms |
460 KB |
Output is correct |
8 |
Correct |
1 ms |
332 KB |
Output is correct |
9 |
Correct |
1 ms |
460 KB |
Output is correct |
10 |
Correct |
1 ms |
460 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
1 ms |
204 KB |
Output is correct |
2 |
Correct |
0 ms |
204 KB |
Output is correct |
3 |
Correct |
0 ms |
204 KB |
Output is correct |
4 |
Correct |
0 ms |
204 KB |
Output is correct |
5 |
Correct |
0 ms |
204 KB |
Output is correct |
6 |
Correct |
59 ms |
14964 KB |
Output is correct |
7 |
Correct |
44 ms |
11368 KB |
Output is correct |
8 |
Correct |
42 ms |
11052 KB |
Output is correct |
9 |
Correct |
46 ms |
12296 KB |
Output is correct |
10 |
Correct |
76 ms |
18268 KB |
Output is correct |
11 |
Correct |
52 ms |
18260 KB |
Output is correct |
12 |
Correct |
40 ms |
17664 KB |
Output is correct |
13 |
Correct |
37 ms |
16052 KB |
Output is correct |
14 |
Correct |
23 ms |
10560 KB |
Output is correct |
15 |
Correct |
45 ms |
20440 KB |
Output is correct |
16 |
Correct |
1 ms |
460 KB |
Output is correct |
17 |
Correct |
1 ms |
460 KB |
Output is correct |
18 |
Correct |
1 ms |
332 KB |
Output is correct |
19 |
Correct |
1 ms |
460 KB |
Output is correct |
20 |
Correct |
1 ms |
460 KB |
Output is correct |
21 |
Correct |
24 ms |
4864 KB |
Output is correct |
22 |
Correct |
13 ms |
4176 KB |
Output is correct |
23 |
Correct |
99 ms |
19408 KB |
Output is correct |
24 |
Correct |
69 ms |
13884 KB |
Output is correct |
25 |
Correct |
64 ms |
13760 KB |
Output is correct |
26 |
Correct |
41 ms |
9232 KB |
Output is correct |
27 |
Correct |
61 ms |
10884 KB |
Output is correct |
28 |
Correct |
84 ms |
14464 KB |
Output is correct |
29 |
Correct |
44 ms |
9924 KB |
Output is correct |
30 |
Correct |
111 ms |
20384 KB |
Output is correct |