//subtask3
#include <iostream>
#include <vector>
#include <algorithm>
using namespace std;
using ll = long long;
vector <vector <int>> adj;
vector <int> vals;
struct DSU {
vector <int> link, sz, mx_val;
DSU (int s) {
link = sz = mx_val = vector <int> (s+1);
for (int i = 1; i <= s; i++) {
link[i] = i;
sz[i] = 1;
mx_val[i] = vals[i];
}
}
int head(int x) {
while (x != link[x])
x = link[x];
return x;
}
void unite(int a, int b) {
a = head(a);
b = head(b);
if (a == b)
return;
if (sz[a] < sz[b])
swap(a, b);
sz[a] += sz[b];
link[b] = a;
mx_val[a] = max(mx_val[a], mx_val[b]);
}
ll get_mx_val(int x) {
return mx_val[head(x)];
}
};
bool comp(int a, int b) {
return vals[a] < vals[b];
}
int main() {
int n;
cin >> n;
vals.resize(n+1);
adj.resize(n+1);
for (int i = 1; i <= n; i++)
cin >> vals[i];
for (int i = 0; i < n-1; i++) {
int a, b;
cin >> a >> b;
adj[a].push_back(b);
adj[b].push_back(a);
}
DSU dsu(n+1);
vector <int> ord(n+1);
for (int i = 1; i <= n; i++)
ord[i] = i;
sort(ord.begin(), ord.end(), comp);
vector <bool> activated(n+1);
ll ans = 0;
for (int i = 1; i <= n; i++) {
int id = ord[i];
activated[id] = true;
ll added = 0;
for (auto j : adj[id]) {
if (activated[j]) {
added++;
ans += dsu.get_mx_val(j);
dsu.unite(j, id);
}
}
ans += added * vals[id];
}
cout << ans << '\n';
}
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
0 ms |
348 KB |
Output is correct |
2 |
Correct |
0 ms |
348 KB |
Output is correct |
3 |
Correct |
0 ms |
348 KB |
Output is correct |
4 |
Correct |
0 ms |
348 KB |
Output is correct |
5 |
Correct |
0 ms |
440 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
75 ms |
8068 KB |
Output is correct |
2 |
Correct |
56 ms |
6228 KB |
Output is correct |
3 |
Correct |
59 ms |
6336 KB |
Output is correct |
4 |
Correct |
60 ms |
6736 KB |
Output is correct |
5 |
Correct |
92 ms |
9732 KB |
Output is correct |
6 |
Correct |
81 ms |
9556 KB |
Output is correct |
7 |
Correct |
71 ms |
8668 KB |
Output is correct |
8 |
Correct |
69 ms |
7724 KB |
Output is correct |
9 |
Correct |
42 ms |
5184 KB |
Output is correct |
10 |
Correct |
81 ms |
9944 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
0 ms |
348 KB |
Output is correct |
2 |
Correct |
0 ms |
348 KB |
Output is correct |
3 |
Correct |
0 ms |
348 KB |
Output is correct |
4 |
Correct |
0 ms |
348 KB |
Output is correct |
5 |
Correct |
0 ms |
440 KB |
Output is correct |
6 |
Correct |
1 ms |
600 KB |
Output is correct |
7 |
Correct |
1 ms |
348 KB |
Output is correct |
8 |
Correct |
1 ms |
348 KB |
Output is correct |
9 |
Correct |
1 ms |
348 KB |
Output is correct |
10 |
Correct |
1 ms |
448 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
0 ms |
348 KB |
Output is correct |
2 |
Correct |
0 ms |
348 KB |
Output is correct |
3 |
Correct |
0 ms |
348 KB |
Output is correct |
4 |
Correct |
0 ms |
348 KB |
Output is correct |
5 |
Correct |
0 ms |
440 KB |
Output is correct |
6 |
Correct |
75 ms |
8068 KB |
Output is correct |
7 |
Correct |
56 ms |
6228 KB |
Output is correct |
8 |
Correct |
59 ms |
6336 KB |
Output is correct |
9 |
Correct |
60 ms |
6736 KB |
Output is correct |
10 |
Correct |
92 ms |
9732 KB |
Output is correct |
11 |
Correct |
81 ms |
9556 KB |
Output is correct |
12 |
Correct |
71 ms |
8668 KB |
Output is correct |
13 |
Correct |
69 ms |
7724 KB |
Output is correct |
14 |
Correct |
42 ms |
5184 KB |
Output is correct |
15 |
Correct |
81 ms |
9944 KB |
Output is correct |
16 |
Correct |
1 ms |
600 KB |
Output is correct |
17 |
Correct |
1 ms |
348 KB |
Output is correct |
18 |
Correct |
1 ms |
348 KB |
Output is correct |
19 |
Correct |
1 ms |
348 KB |
Output is correct |
20 |
Correct |
1 ms |
448 KB |
Output is correct |
21 |
Correct |
21 ms |
2652 KB |
Output is correct |
22 |
Correct |
17 ms |
2140 KB |
Output is correct |
23 |
Correct |
110 ms |
9416 KB |
Output is correct |
24 |
Correct |
62 ms |
6736 KB |
Output is correct |
25 |
Correct |
62 ms |
6740 KB |
Output is correct |
26 |
Correct |
40 ms |
4692 KB |
Output is correct |
27 |
Correct |
47 ms |
5476 KB |
Output is correct |
28 |
Correct |
62 ms |
6992 KB |
Output is correct |
29 |
Correct |
38 ms |
4688 KB |
Output is correct |
30 |
Correct |
94 ms |
10068 KB |
Output is correct |