#include <bits/stdc++.h>
#define ST first
#define ND second
#define PB push_back
using namespace std;
using ll = long long;
using pi = pair<int,int>;
using vi = vector<int>;
const int nax = 100 * 1000 + 10;
int n;
pi val[nax];
int par[nax], siz[nax], mx[nax];
vi V[nax];
int Fund(int x) {
if(par[x] != x) par[x] = Fund(par[x]);
return par[x];
}
void Onion(int a, int b) {
a = Fund(a); b = Fund(b);
if(a == b) return;
if(siz[a] < siz[b]) swap(a, b);
siz[a] += siz[b];
mx[a] = max(mx[a], mx[b]);
par[b] = a;
}
ll ans;
int main() {
ios_base::sync_with_stdio(0);
cin.tie(0);
cin >> n;
for(int i = 1; i <= n; ++i) {
par[i] = i;
siz[i] = 1;
cin >> mx[i];
val[i] = {mx[i], i};
}
for(int a,b,i = 1; i < n; ++i) {
cin >> a >> b;
V[a].PB(b);
V[b].PB(a);
}
sort(val + 1, val + n + 1);
for(int i = 1; i <= n; ++i) {
int u = val[i].ND;
for(auto nbh : V[u]) {
if(mx[Fund(nbh)] <= val[i].ST) {
if(Fund(nbh) != Fund(u)) {
ans += val[i].ST;
ans += mx[Fund(nbh)];
Onion(nbh, u);
}
}
}
}
cout << ans;
}
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
2 ms |
2636 KB |
Output is correct |
2 |
Correct |
2 ms |
2680 KB |
Output is correct |
3 |
Correct |
2 ms |
2636 KB |
Output is correct |
4 |
Correct |
2 ms |
2636 KB |
Output is correct |
5 |
Correct |
2 ms |
2636 KB |
Output is correct |
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
48 ms |
6712 KB |
Output is correct |
2 |
Correct |
38 ms |
5776 KB |
Output is correct |
3 |
Correct |
35 ms |
5700 KB |
Output is correct |
4 |
Correct |
41 ms |
5956 KB |
Output is correct |
5 |
Correct |
61 ms |
7708 KB |
Output is correct |
6 |
Correct |
51 ms |
7640 KB |
Output is correct |
7 |
Correct |
41 ms |
7112 KB |
Output is correct |
8 |
Correct |
37 ms |
6708 KB |
Output is correct |
9 |
Correct |
25 ms |
5324 KB |
Output is correct |
10 |
Correct |
47 ms |
7744 KB |
Output is correct |
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
2 ms |
2636 KB |
Output is correct |
2 |
Correct |
2 ms |
2680 KB |
Output is correct |
3 |
Correct |
2 ms |
2636 KB |
Output is correct |
4 |
Correct |
2 ms |
2636 KB |
Output is correct |
5 |
Correct |
2 ms |
2636 KB |
Output is correct |
6 |
Correct |
2 ms |
2636 KB |
Output is correct |
7 |
Correct |
2 ms |
2636 KB |
Output is correct |
8 |
Correct |
2 ms |
2636 KB |
Output is correct |
9 |
Correct |
2 ms |
2636 KB |
Output is correct |
10 |
Correct |
2 ms |
2636 KB |
Output is correct |
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
2 ms |
2636 KB |
Output is correct |
2 |
Correct |
2 ms |
2680 KB |
Output is correct |
3 |
Correct |
2 ms |
2636 KB |
Output is correct |
4 |
Correct |
2 ms |
2636 KB |
Output is correct |
5 |
Correct |
2 ms |
2636 KB |
Output is correct |
6 |
Correct |
48 ms |
6712 KB |
Output is correct |
7 |
Correct |
38 ms |
5776 KB |
Output is correct |
8 |
Correct |
35 ms |
5700 KB |
Output is correct |
9 |
Correct |
41 ms |
5956 KB |
Output is correct |
10 |
Correct |
61 ms |
7708 KB |
Output is correct |
11 |
Correct |
51 ms |
7640 KB |
Output is correct |
12 |
Correct |
41 ms |
7112 KB |
Output is correct |
13 |
Correct |
37 ms |
6708 KB |
Output is correct |
14 |
Correct |
25 ms |
5324 KB |
Output is correct |
15 |
Correct |
47 ms |
7744 KB |
Output is correct |
16 |
Correct |
2 ms |
2636 KB |
Output is correct |
17 |
Correct |
2 ms |
2636 KB |
Output is correct |
18 |
Correct |
2 ms |
2636 KB |
Output is correct |
19 |
Correct |
2 ms |
2636 KB |
Output is correct |
20 |
Correct |
2 ms |
2636 KB |
Output is correct |
21 |
Correct |
15 ms |
3912 KB |
Output is correct |
22 |
Correct |
13 ms |
3708 KB |
Output is correct |
23 |
Correct |
70 ms |
7640 KB |
Output is correct |
24 |
Correct |
46 ms |
6304 KB |
Output is correct |
25 |
Correct |
52 ms |
6276 KB |
Output is correct |
26 |
Correct |
30 ms |
5032 KB |
Output is correct |
27 |
Correct |
35 ms |
5488 KB |
Output is correct |
28 |
Correct |
54 ms |
6512 KB |
Output is correct |
29 |
Correct |
33 ms |
5996 KB |
Output is correct |
30 |
Correct |
69 ms |
9924 KB |
Output is correct |