#include <bits/stdc++.h>
//#include <ext/pb_ds/assoc_container.hpp>
//#include <ext/pb_ds/tree_policy.hpp>
//#pragma GCC optimize("unroll-loops")
//#pragma GCC optimize("-O3")
//#pragma GCC optimize("Ofast")
#define N 100005
#define NN 1005000
#define PB push_back
#define M ll(1e9 + 7)
#define all(x) x.begin(), x.end()
#define sz(x) int(x.size())
#define pri(x) cout << x << endl
#define endl '\n'
#define _ << " " <<
#define F first
#define S second
using namespace std;
//using namespace __gnu_pbds;
//typedef tree <int, null_type, less <int>, rb_tree_tag, tree_order_statistics_node_update> oredered_set;
typedef long long ll;
typedef long double ld;
typedef unsigned long long ull;
typedef short int si;
int p[N], mx[N];
int fnd(int x)
{
if (p[x] != x)
p[x] = fnd(p[x]);
return p[x];
}
void link(int a, int b)
{
p[b] = a;
mx[a] = max(mx[a], mx[b]);
}
int a[N];
bool cmp(pair <int, int> x, pair <int, int> y)
{
return max(a[x.F], a[x.S]) < max(a[y.F], a[y.S]);
}
int main()
{
ios_base::sync_with_stdio(0); istream::sync_with_stdio(0); cin.tie(0); cout.tie(0);
//freopen("1.in", "r", stdin);
int n;
cin >> n;
for (int i = 1; i <= n; i++) cin >> a[i];
vector <pair <int, int> > pr(n - 1);
for (int i = 1; i < n; i++)
{
int x, y;
cin >> x >> y;
pr[i - 1] = {x, y};
}
sort(all(pr), cmp);
for (int i = 1; i <= n; i++)
{
p[i] = i;
mx[i] = a[i];
}
ll ans = 0;
for (auto it : pr)
{
int l = fnd(it.F), r = fnd(it.S);
ans += mx[l] + mx[r];
link(l, r);
}
pri(ans);
}
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
1 ms |
364 KB |
Output is correct |
2 |
Correct |
1 ms |
364 KB |
Output is correct |
3 |
Correct |
1 ms |
364 KB |
Output is correct |
4 |
Correct |
1 ms |
364 KB |
Output is correct |
5 |
Correct |
1 ms |
364 KB |
Output is correct |
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
38 ms |
2028 KB |
Output is correct |
2 |
Correct |
28 ms |
1516 KB |
Output is correct |
3 |
Correct |
29 ms |
1540 KB |
Output is correct |
4 |
Correct |
31 ms |
1644 KB |
Output is correct |
5 |
Correct |
47 ms |
2284 KB |
Output is correct |
6 |
Correct |
56 ms |
2412 KB |
Output is correct |
7 |
Correct |
44 ms |
2028 KB |
Output is correct |
8 |
Correct |
41 ms |
1920 KB |
Output is correct |
9 |
Correct |
27 ms |
1388 KB |
Output is correct |
10 |
Correct |
48 ms |
2284 KB |
Output is correct |
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
1 ms |
364 KB |
Output is correct |
2 |
Correct |
1 ms |
364 KB |
Output is correct |
3 |
Correct |
1 ms |
364 KB |
Output is correct |
4 |
Correct |
1 ms |
364 KB |
Output is correct |
5 |
Correct |
1 ms |
364 KB |
Output is correct |
6 |
Correct |
1 ms |
384 KB |
Output is correct |
7 |
Correct |
1 ms |
364 KB |
Output is correct |
8 |
Correct |
1 ms |
364 KB |
Output is correct |
9 |
Correct |
1 ms |
364 KB |
Output is correct |
10 |
Correct |
1 ms |
364 KB |
Output is correct |
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
1 ms |
364 KB |
Output is correct |
2 |
Correct |
1 ms |
364 KB |
Output is correct |
3 |
Correct |
1 ms |
364 KB |
Output is correct |
4 |
Correct |
1 ms |
364 KB |
Output is correct |
5 |
Correct |
1 ms |
364 KB |
Output is correct |
6 |
Correct |
38 ms |
2028 KB |
Output is correct |
7 |
Correct |
28 ms |
1516 KB |
Output is correct |
8 |
Correct |
29 ms |
1540 KB |
Output is correct |
9 |
Correct |
31 ms |
1644 KB |
Output is correct |
10 |
Correct |
47 ms |
2284 KB |
Output is correct |
11 |
Correct |
56 ms |
2412 KB |
Output is correct |
12 |
Correct |
44 ms |
2028 KB |
Output is correct |
13 |
Correct |
41 ms |
1920 KB |
Output is correct |
14 |
Correct |
27 ms |
1388 KB |
Output is correct |
15 |
Correct |
48 ms |
2284 KB |
Output is correct |
16 |
Correct |
1 ms |
384 KB |
Output is correct |
17 |
Correct |
1 ms |
364 KB |
Output is correct |
18 |
Correct |
1 ms |
364 KB |
Output is correct |
19 |
Correct |
1 ms |
364 KB |
Output is correct |
20 |
Correct |
1 ms |
364 KB |
Output is correct |
21 |
Correct |
11 ms |
748 KB |
Output is correct |
22 |
Correct |
9 ms |
748 KB |
Output is correct |
23 |
Correct |
46 ms |
2156 KB |
Output is correct |
24 |
Correct |
32 ms |
1644 KB |
Output is correct |
25 |
Correct |
32 ms |
1644 KB |
Output is correct |
26 |
Correct |
21 ms |
1260 KB |
Output is correct |
27 |
Correct |
26 ms |
1388 KB |
Output is correct |
28 |
Correct |
34 ms |
1772 KB |
Output is correct |
29 |
Correct |
22 ms |
1260 KB |
Output is correct |
30 |
Correct |
49 ms |
2284 KB |
Output is correct |