#include <bits/stdc++.h>
using namespace std;
#define ll long long
#define ar array
#define debug(x) cerr << "[" << #x << "] = [" << x << "]\n"
template<class A, class B> ostream& operator<< (ostream& out, pair<A, B> p) {
return out << '[' << p.first << ", " << p.second << ']';
}
template<class T> ostream& operator<< (ostream& out, vector<T> v) {
out << '[';
for (int i = 0; i < v.size(); ++i) {
if (i > 0) {
out << ", ";
}
out << v[i];
}
return out << ']';
}
template<class T> ostream& operator<< (ostream& out, set<T> s) {
return out << (vector<T>(s.begin(), s.end()));
}
const int mxN = 100000;
int n, p[mxN], mx[mxN], offset[mxN];
ll ans = 0;
set<pair<int, int>> adj[mxN];
set<ar<int, 3>> small;
int find(int i) {
return i ^ p[i] ? p[i] = find(p[i]) : i;
}
void merge(int a, int b) {
if (adj[a].size() < adj[b].size()) swap(a, b);
p[b] = a;
if (mx[a] >= mx[b]) {
for (const pair<int, int>& p : adj[b]) {
if (find(a) != find(p.second))
adj[a].emplace(p.first + offset[b] - offset[a] + mx[a] - mx[b], p.second);
}
}
else {
offset[a] += mx[b] - mx[a];
for (const pair<int, int>& p : adj[b]) {
if (find(a) != find(p.second))
adj[a].emplace(p.first + offset[b] - offset[a], p.second);
}
}
set<pair<int, int>>().swap(adj[b]);
mx[a] = max(mx[a], mx[b]);
while(!adj[a].empty()) {
pair<int, int> p = *adj[a].begin();
if (find(p.second) != a && mx[a] + mx[find(p.second)] - offset[a] == p.first) break;
adj[a].erase(adj[a].begin());
if (find(p.second) != a) adj[a].emplace(mx[a] + mx[find(p.second)] - offset[a], find(p.second));
}
//debug(offset[a]);
//debug(adj[a]);
if (!adj[a].empty()) {
pair<int, int> p = *adj[a].begin();
assert(p.first + offset[a] == mx[a] + mx[find(p.second)]);
small.insert({p.first + offset[a], a, p.second});
}
}
int main() {
ios::sync_with_stdio(0);
cin.tie(0);
cin >> n;
for (int i = 0; i < n; ++i) {
cin >> mx[i];
p[i] = i;
}
for (int i = 1; i < n; ++i) {
int a, b; cin >> a >> b, --a, --b;
adj[a].emplace(mx[a] + mx[b], b);
adj[b].emplace(mx[a] + mx[b], a);
small.insert({mx[a] + mx[b], a, b});
}
while(!small.empty()) {
ar<int, 3> t = *small.begin(); small.erase(small.begin());
int a = find(t[1]), b = find(t[2]);
if (a == b || t[0] != mx[a] + mx[b]) continue; // fraud...
//cerr << a << " " << b << "\n";
ans += t[0];
assert(!adj[a].empty() && !adj[b].empty());
merge(a, b);
}
cout << ans;
return 0;
}
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
4 ms |
5100 KB |
Output is correct |
2 |
Correct |
5 ms |
5100 KB |
Output is correct |
3 |
Correct |
6 ms |
5100 KB |
Output is correct |
4 |
Correct |
6 ms |
5100 KB |
Output is correct |
5 |
Correct |
5 ms |
5100 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
230 ms |
20444 KB |
Output is correct |
2 |
Correct |
172 ms |
16748 KB |
Output is correct |
3 |
Correct |
157 ms |
16364 KB |
Output is correct |
4 |
Correct |
173 ms |
17700 KB |
Output is correct |
5 |
Correct |
309 ms |
24152 KB |
Output is correct |
6 |
Correct |
101 ms |
23660 KB |
Output is correct |
7 |
Correct |
86 ms |
21112 KB |
Output is correct |
8 |
Correct |
98 ms |
19692 KB |
Output is correct |
9 |
Correct |
57 ms |
14684 KB |
Output is correct |
10 |
Correct |
105 ms |
23660 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
4 ms |
5100 KB |
Output is correct |
2 |
Correct |
5 ms |
5100 KB |
Output is correct |
3 |
Correct |
6 ms |
5100 KB |
Output is correct |
4 |
Correct |
6 ms |
5100 KB |
Output is correct |
5 |
Correct |
5 ms |
5100 KB |
Output is correct |
6 |
Correct |
5 ms |
5228 KB |
Output is correct |
7 |
Correct |
5 ms |
5228 KB |
Output is correct |
8 |
Correct |
5 ms |
5376 KB |
Output is correct |
9 |
Correct |
5 ms |
5244 KB |
Output is correct |
10 |
Correct |
5 ms |
5376 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
4 ms |
5100 KB |
Output is correct |
2 |
Correct |
5 ms |
5100 KB |
Output is correct |
3 |
Correct |
6 ms |
5100 KB |
Output is correct |
4 |
Correct |
6 ms |
5100 KB |
Output is correct |
5 |
Correct |
5 ms |
5100 KB |
Output is correct |
6 |
Correct |
230 ms |
20444 KB |
Output is correct |
7 |
Correct |
172 ms |
16748 KB |
Output is correct |
8 |
Correct |
157 ms |
16364 KB |
Output is correct |
9 |
Correct |
173 ms |
17700 KB |
Output is correct |
10 |
Correct |
309 ms |
24152 KB |
Output is correct |
11 |
Correct |
101 ms |
23660 KB |
Output is correct |
12 |
Correct |
86 ms |
21112 KB |
Output is correct |
13 |
Correct |
98 ms |
19692 KB |
Output is correct |
14 |
Correct |
57 ms |
14684 KB |
Output is correct |
15 |
Correct |
105 ms |
23660 KB |
Output is correct |
16 |
Correct |
5 ms |
5228 KB |
Output is correct |
17 |
Correct |
5 ms |
5228 KB |
Output is correct |
18 |
Correct |
5 ms |
5376 KB |
Output is correct |
19 |
Correct |
5 ms |
5244 KB |
Output is correct |
20 |
Correct |
5 ms |
5376 KB |
Output is correct |
21 |
Correct |
47 ms |
9456 KB |
Output is correct |
22 |
Correct |
40 ms |
8684 KB |
Output is correct |
23 |
Correct |
347 ms |
23280 KB |
Output is correct |
24 |
Correct |
202 ms |
17984 KB |
Output is correct |
25 |
Correct |
202 ms |
17900 KB |
Output is correct |
26 |
Correct |
124 ms |
13608 KB |
Output is correct |
27 |
Correct |
149 ms |
15108 KB |
Output is correct |
28 |
Correct |
250 ms |
18548 KB |
Output is correct |
29 |
Correct |
142 ms |
14188 KB |
Output is correct |
30 |
Correct |
369 ms |
24032 KB |
Output is correct |