/*
+----+----+----+----+----+----+----+----+----+----+----+----+----+----+----+----+----+----+----+----+----+----+----+----+----+----+----+
|\ \/|\/ /|\ \/|\/ /|\ \/|\/ /|\ \/|\/ /|\ \/|\/ /|\ \/|\/ /|\ \/|\/ /|\ \/|\/ /|\ \/|\/ /|\ \/|\/ /|\ \/|\/ /|\ \/|\/ /|\ \/|\/ /|\ \/|
| \/ | \/ | \/ | \/ | \/ | \/ | \/ | \/ | \/ | \/ | \/ | \/ | \/ | \/ | \/ | \/ | \/ | \/ | \/ | \/ | \/ | \/ | \/ | \/ | \/ | \/ | \/ |
|\/ | \/|\/ | \/|\/ | \/|\/ | \/|\/ | \/|\/ | \/|\/ | \/|\/ | \/|\/ | \/|\/ | \/|\/ | \/|\/ | \/|\/ | \/|\/ |
|/ | \|/ | \|/ | \|/ | \|/ | \|/ | \|/ | \|/ | \|/ | \|/ | \|/ | \|/ | \|/ | \|/ |
+----+----+----+----+----+----+----+----+----+----+----+----+----+----+----+----+----+----+----+----+----+----+----+----+----+----+----+
|\ | /|\ | /|\ | /|\ | /|\ | /|\ | /|\ | /|\ | /|\ | /|\ | /|\ | /|\ | /|\ | /|\ |
|/\ | /\|/\ | /\|/\ | /\|/\ | /\|/\ | /\|/\ | /\|/\ | /\|/\ | /\|/\ | /\|/\ | /\|/\ | /\|/\ | /\|/\ | /\|/\ |
| /\ | /\ | /\ | /\ | /\ | /\ | /\ | /\ | /\ | /\ | /\ | /\ | /\ | /\ | /\ | /\ | /\ | /\ | /\ | /\ | /\ | /\ | /\ | /\ | /\ | /\ | /\ |
|/ /\|/\ \|/ /\|/\ \|/ /\|/\ \|/ /\|/\ \|/ /\|/\ \|/ /\|/\ \|/ /\|/\ \|/ /\|/\ \|/ /\|/\ \|/ /\|/\ \|/ /\|/\ \|/ /\|/\ \|/ /\|/\ \|/ /\|
+----+----+----+----+----+----+----+----+----+----+----+----+----+----+----+----+----+----+----+----+----+----+----+----+----+----+----+
*/
#include <bits/stdc++.h>
#define fore(i, a, b) for (signed i = (a), i##_last = (b); i < i##_last; ++i)
#define fort(i, a, b) for (signed i = (a), i##_last = (b); i <= i##_last; ++i)
#define ford(i, a, b) for (signed i = (a), i##_last = (b); i >= i##_last; --i)
#define fi first
#define se second
#define pb push_back
#define sz(x) ((int)(x).size())
#define all(x) (x).begin(), (x).end()
#define rall(x) (x).rbegin(), (x).rend()
using namespace std;
using ll = long long;
using ld = long double;
template<class A, class B> bool maxi(A &a, const B &b) {return (a < b) ? (a = b, true):false;};
template<class A, class B> bool mini(A &a, const B &b) {return (a > b) ? (a = b, true):false;};
typedef unsigned long long ull;
typedef pair<int, int> ii;
typedef vector<ll> vi;
typedef vector<ii> vii;
typedef vector<vi> vvi;
typedef vector<vii> vvii;
struct DisjointSet {
private:
std::vector<int> r, maximum;
public:
DisjointSet() {};
DisjointSet(const int n): r(n, -1) {};
void resize(const int n) {
r.resize(n, -1);
maximum.resize(n);
}
void reload() {
std::fill(r.begin(), r.end(), -1);
};
int getRoot(const int x) const {
return r[x] < 0 ? x : getRoot(r[x]);
}
int unite(int x, int y) {
x = getRoot(x);
y = getRoot(y);
if (x == y)
return 0;
const int res = maximum[x] + maximum[y];
if (r[x] > r[y])
std::swap(x, y);
maximum[x] = max(maximum[x], maximum[y]);
r[x] += r[y];
r[y] = x;
return res;
}
bool checkConnected(const int x, const int y) const {
return getRoot(x) == getRoot(y);
}
int getTreeSize(const int x) const {
return -r[getRoot(x)];
}
int& getMaximum(const int x) {
return maximum[getRoot(x)];
}
};
const int maxN = 100005;
ll res;
int n, t[maxN];
vi p, adj[maxN];
DisjointSet dsu;
void input() {
int x, y;
cin >> n;
p.resize(n);
dsu.resize(n);
fore(i, 0, n) {
cin >> t[i];
p[i] = i;
dsu.getMaximum(i) = t[i];
}
fore(_, 1, n) {
cin >> x >> y;
--x;
--y;
adj[x].pb(y);
adj[y].pb(x);
}
}
void solve() {
sort(all(p), [&](const int &x, const int &y) -> bool {
return t[x] < t[y];
});
for (const int &u : p)
for (const int &v : adj[u]) {
if (t[v] > t[u])
continue;
res += dsu.unite(u, v);
}
cout << res << '\n';
}
int main() {
#ifdef LOCAL
freopen("input.INP", "r", stdin);
#endif // LOCAL
cin.tie(0) -> sync_with_stdio(0);
cout.tie(0);
input();
solve();
return 0;
}
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
1 ms |
2644 KB |
Output is correct |
2 |
Correct |
1 ms |
2644 KB |
Output is correct |
3 |
Correct |
1 ms |
2644 KB |
Output is correct |
4 |
Correct |
2 ms |
2676 KB |
Output is correct |
5 |
Correct |
3 ms |
2772 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
54 ms |
6772 KB |
Output is correct |
2 |
Correct |
37 ms |
7116 KB |
Output is correct |
3 |
Correct |
34 ms |
7008 KB |
Output is correct |
4 |
Correct |
36 ms |
7496 KB |
Output is correct |
5 |
Correct |
58 ms |
9844 KB |
Output is correct |
6 |
Correct |
43 ms |
9792 KB |
Output is correct |
7 |
Correct |
42 ms |
8812 KB |
Output is correct |
8 |
Correct |
35 ms |
8268 KB |
Output is correct |
9 |
Correct |
25 ms |
6256 KB |
Output is correct |
10 |
Correct |
43 ms |
9848 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
1 ms |
2644 KB |
Output is correct |
2 |
Correct |
1 ms |
2644 KB |
Output is correct |
3 |
Correct |
1 ms |
2644 KB |
Output is correct |
4 |
Correct |
2 ms |
2676 KB |
Output is correct |
5 |
Correct |
3 ms |
2772 KB |
Output is correct |
6 |
Correct |
2 ms |
2644 KB |
Output is correct |
7 |
Correct |
3 ms |
2644 KB |
Output is correct |
8 |
Correct |
2 ms |
2644 KB |
Output is correct |
9 |
Correct |
2 ms |
2644 KB |
Output is correct |
10 |
Correct |
2 ms |
2692 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
1 ms |
2644 KB |
Output is correct |
2 |
Correct |
1 ms |
2644 KB |
Output is correct |
3 |
Correct |
1 ms |
2644 KB |
Output is correct |
4 |
Correct |
2 ms |
2676 KB |
Output is correct |
5 |
Correct |
3 ms |
2772 KB |
Output is correct |
6 |
Correct |
54 ms |
6772 KB |
Output is correct |
7 |
Correct |
37 ms |
7116 KB |
Output is correct |
8 |
Correct |
34 ms |
7008 KB |
Output is correct |
9 |
Correct |
36 ms |
7496 KB |
Output is correct |
10 |
Correct |
58 ms |
9844 KB |
Output is correct |
11 |
Correct |
43 ms |
9792 KB |
Output is correct |
12 |
Correct |
42 ms |
8812 KB |
Output is correct |
13 |
Correct |
35 ms |
8268 KB |
Output is correct |
14 |
Correct |
25 ms |
6256 KB |
Output is correct |
15 |
Correct |
43 ms |
9848 KB |
Output is correct |
16 |
Correct |
2 ms |
2644 KB |
Output is correct |
17 |
Correct |
3 ms |
2644 KB |
Output is correct |
18 |
Correct |
2 ms |
2644 KB |
Output is correct |
19 |
Correct |
2 ms |
2644 KB |
Output is correct |
20 |
Correct |
2 ms |
2692 KB |
Output is correct |
21 |
Correct |
15 ms |
4456 KB |
Output is correct |
22 |
Correct |
17 ms |
4100 KB |
Output is correct |
23 |
Correct |
77 ms |
10080 KB |
Output is correct |
24 |
Correct |
52 ms |
7848 KB |
Output is correct |
25 |
Correct |
36 ms |
7784 KB |
Output is correct |
26 |
Correct |
24 ms |
6028 KB |
Output is correct |
27 |
Correct |
31 ms |
6740 KB |
Output is correct |
28 |
Correct |
49 ms |
7928 KB |
Output is correct |
29 |
Correct |
42 ms |
6248 KB |
Output is correct |
30 |
Correct |
78 ms |
10472 KB |
Output is correct |