#include <bits/stdc++.h>
using namespace std;
#define int long long
int n;
int ar[500005];
int uf[500005];
int umx[500005];
int fin(int x){
if(uf[x]==x){return x;}
uf[x]=fin(uf[x]);
return uf[x];
}
void mrg(int a,int b){
int pa=fin(a);int pb=fin(b);
if(pa==pb){return;}
uf[pa]=pb;
umx[pb]=max(umx[pa],umx[pb]);
}
struct edge{
int a;int b;int v;
bool operator<(const edge &ee)const{
if(v>ee.v){return 1;}
return 0;
}
}e[500005];
signed main() {
cin>>n;
for(int i=1;i<=n;i++){
cin>>ar[i];
uf[i]=i;
umx[i]=ar[i];
}
for(int i=1;i<=n-1;i++){
cin>>e[i].a>>e[i].b;
e[i].v=max(ar[e[i].a],ar[e[i].b]);
}
sort(e+1,e+n);
reverse(e+1,e+n);
int ans=0;
for(int i=1;i<=n-1;i++){
int a;int b;
a=e[i].a;b=e[i].b;
ans+=umx[fin(a)]+umx[fin(b)];
mrg(a,b);
}
cout<<ans<<endl;
return 0;
}
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
0 ms |
212 KB |
Output is correct |
2 |
Correct |
1 ms |
296 KB |
Output is correct |
3 |
Correct |
1 ms |
340 KB |
Output is correct |
4 |
Correct |
1 ms |
212 KB |
Output is correct |
5 |
Correct |
0 ms |
340 KB |
Output is correct |
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
64 ms |
4080 KB |
Output is correct |
2 |
Correct |
48 ms |
4524 KB |
Output is correct |
3 |
Correct |
44 ms |
4336 KB |
Output is correct |
4 |
Correct |
49 ms |
4824 KB |
Output is correct |
5 |
Correct |
74 ms |
7020 KB |
Output is correct |
6 |
Correct |
74 ms |
7760 KB |
Output is correct |
7 |
Correct |
60 ms |
6436 KB |
Output is correct |
8 |
Correct |
57 ms |
5996 KB |
Output is correct |
9 |
Correct |
35 ms |
4080 KB |
Output is correct |
10 |
Correct |
69 ms |
7500 KB |
Output is correct |
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
0 ms |
212 KB |
Output is correct |
2 |
Correct |
1 ms |
296 KB |
Output is correct |
3 |
Correct |
1 ms |
340 KB |
Output is correct |
4 |
Correct |
1 ms |
212 KB |
Output is correct |
5 |
Correct |
0 ms |
340 KB |
Output is correct |
6 |
Correct |
1 ms |
340 KB |
Output is correct |
7 |
Correct |
1 ms |
340 KB |
Output is correct |
8 |
Correct |
1 ms |
340 KB |
Output is correct |
9 |
Correct |
1 ms |
312 KB |
Output is correct |
10 |
Correct |
1 ms |
340 KB |
Output is correct |
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
0 ms |
212 KB |
Output is correct |
2 |
Correct |
1 ms |
296 KB |
Output is correct |
3 |
Correct |
1 ms |
340 KB |
Output is correct |
4 |
Correct |
1 ms |
212 KB |
Output is correct |
5 |
Correct |
0 ms |
340 KB |
Output is correct |
6 |
Correct |
64 ms |
4080 KB |
Output is correct |
7 |
Correct |
48 ms |
4524 KB |
Output is correct |
8 |
Correct |
44 ms |
4336 KB |
Output is correct |
9 |
Correct |
49 ms |
4824 KB |
Output is correct |
10 |
Correct |
74 ms |
7020 KB |
Output is correct |
11 |
Correct |
74 ms |
7760 KB |
Output is correct |
12 |
Correct |
60 ms |
6436 KB |
Output is correct |
13 |
Correct |
57 ms |
5996 KB |
Output is correct |
14 |
Correct |
35 ms |
4080 KB |
Output is correct |
15 |
Correct |
69 ms |
7500 KB |
Output is correct |
16 |
Correct |
1 ms |
340 KB |
Output is correct |
17 |
Correct |
1 ms |
340 KB |
Output is correct |
18 |
Correct |
1 ms |
340 KB |
Output is correct |
19 |
Correct |
1 ms |
312 KB |
Output is correct |
20 |
Correct |
1 ms |
340 KB |
Output is correct |
21 |
Correct |
17 ms |
1828 KB |
Output is correct |
22 |
Correct |
16 ms |
1520 KB |
Output is correct |
23 |
Correct |
73 ms |
6712 KB |
Output is correct |
24 |
Correct |
51 ms |
4844 KB |
Output is correct |
25 |
Correct |
51 ms |
4812 KB |
Output is correct |
26 |
Correct |
35 ms |
3268 KB |
Output is correct |
27 |
Correct |
39 ms |
3812 KB |
Output is correct |
28 |
Correct |
46 ms |
4744 KB |
Output is correct |
29 |
Correct |
31 ms |
3392 KB |
Output is correct |
30 |
Correct |
78 ms |
6988 KB |
Output is correct |