/*
* author: Araragi
*/
// 3
#include <bits/stdc++.h>
using namespace std;
#define pb push_back
#define F first
#define S second
//using namespace __gnu_pbds;
//typedef tree <int, null_type, less_equal <int> , rb_tree_tag, tree_order_statistics_node_update> ordered_set;
typedef long long ll;
typedef long double ld;
typedef unsigned long long ull;
ll cost[100001];
vector<ll> dsu;
ll ans;
inline ll get(ll x)
{
return (dsu[x] == x ? x : dsu[x] = get(dsu[x]));
}
inline bool unite(ll x, ll y)
{
ll xx = get(x);
ll yy = get(y);
if (xx != yy)
{
dsu[xx] = yy;
ans += cost[xx];
ans += cost[yy];
cost[yy] = max(cost[yy], cost[xx]);
return true;
}
return false;
}
bool cmp(pair<ll, ll> x, pair<ll, ll> y)
{
return max(cost[x.F], cost[x.S]) < max(cost[y.F], cost[y.S]);
}
int main()
{
//ifstream cin("vacation.in");
//ofstream cout("vacation.out");
ll n;
cin >> n;
for (ll i = 1; i <= n; i++)
cin >> cost[i];
dsu.resize(n + 1);
iota(dsu.begin(), dsu.end(), 0);
vector<pair<ll, ll> > edges;
for (ll i = 1; i < n; i++)
{
ll x, y;
cin >> x >> y;
edges.pb({x, y});
}
sort(edges.begin(), edges.end(), cmp);
for (auto edge : edges)
if (unite(edge.F, edge.S))
{
// without code, need void
}
cout << 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 |
492 KB |
Output is correct |
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
106 ms |
3808 KB |
Output is correct |
2 |
Correct |
87 ms |
2532 KB |
Output is correct |
3 |
Correct |
77 ms |
2660 KB |
Output is correct |
4 |
Correct |
80 ms |
3720 KB |
Output is correct |
5 |
Correct |
120 ms |
4328 KB |
Output is correct |
6 |
Correct |
125 ms |
4444 KB |
Output is correct |
7 |
Correct |
111 ms |
3936 KB |
Output is correct |
8 |
Correct |
115 ms |
3808 KB |
Output is correct |
9 |
Correct |
68 ms |
2528 KB |
Output is correct |
10 |
Correct |
120 ms |
4448 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 |
492 KB |
Output is correct |
6 |
Correct |
2 ms |
364 KB |
Output is correct |
7 |
Correct |
1 ms |
364 KB |
Output is correct |
8 |
Correct |
1 ms |
364 KB |
Output is correct |
9 |
Correct |
2 ms |
364 KB |
Output is correct |
10 |
Correct |
2 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 |
492 KB |
Output is correct |
6 |
Correct |
106 ms |
3808 KB |
Output is correct |
7 |
Correct |
87 ms |
2532 KB |
Output is correct |
8 |
Correct |
77 ms |
2660 KB |
Output is correct |
9 |
Correct |
80 ms |
3720 KB |
Output is correct |
10 |
Correct |
120 ms |
4328 KB |
Output is correct |
11 |
Correct |
125 ms |
4444 KB |
Output is correct |
12 |
Correct |
111 ms |
3936 KB |
Output is correct |
13 |
Correct |
115 ms |
3808 KB |
Output is correct |
14 |
Correct |
68 ms |
2528 KB |
Output is correct |
15 |
Correct |
120 ms |
4448 KB |
Output is correct |
16 |
Correct |
2 ms |
364 KB |
Output is correct |
17 |
Correct |
1 ms |
364 KB |
Output is correct |
18 |
Correct |
1 ms |
364 KB |
Output is correct |
19 |
Correct |
2 ms |
364 KB |
Output is correct |
20 |
Correct |
2 ms |
364 KB |
Output is correct |
21 |
Correct |
34 ms |
1512 KB |
Output is correct |
22 |
Correct |
23 ms |
1384 KB |
Output is correct |
23 |
Correct |
123 ms |
4192 KB |
Output is correct |
24 |
Correct |
85 ms |
3680 KB |
Output is correct |
25 |
Correct |
84 ms |
3808 KB |
Output is correct |
26 |
Correct |
59 ms |
2404 KB |
Output is correct |
27 |
Correct |
65 ms |
2404 KB |
Output is correct |
28 |
Correct |
95 ms |
3808 KB |
Output is correct |
29 |
Correct |
52 ms |
2404 KB |
Output is correct |
30 |
Correct |
125 ms |
4192 KB |
Output is correct |