#include <bits/stdc++.h>
using namespace std;
#define sp << " " <<
#define int long long
#define vi vector<int>
#define pb push_back
#define F(xxx,yyy) for (int xxx=1;xxx<=yyy;xxx++)
#define pii pair<int,int>
const int N = 1e5+1;
vi a(N),dad(N),mx(N);
int find(int x) {
if (x == dad[x]) return x;
return dad[x] = find(dad[x]);
}
void unite(int x,int y) {
mx[find(x)] = max(mx[find(x)],mx[find(y)]);
dad[find(x)] = find(y);
}
void solve() {
int n;
cin >> n;
for (int i=1;i<=n;i++) dad[i] = i;
F(i,n) cin >> a[i];
F(i,n) mx[i] = a[i];
vector<int> edg[n+1];
for (int i=1;i<=n-1;i++) {
int x,y;
cin >> x >> y;
if (a[x] > a[y]) edg[x].pb(y);
else edg[y].pb(x);
}
vi node(n+1);
F(i,n) node[i] = i;
sort(node.begin()+1,node.end(),[&](int p,int r) {return a[p]<a[r];});
int ans = 0;
for (int i=1;i<=n;i++) {
ans+=edg[node[i]].size()*a[node[i]];
int sm = 0;
for (auto it : edg[node[i]]) {
sm+=mx[find(it)];
unite(it,node[i]);
}
ans+=sm;
}
cout << ans << endl;
}
signed main() {
ios_base::sync_with_stdio(0);cin.tie(0);cout.tie(0);
int t = 1;
//cin >> t;
while (t --> 0) solve();
}
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
1 ms |
2652 KB |
Output is correct |
2 |
Correct |
1 ms |
2652 KB |
Output is correct |
3 |
Correct |
1 ms |
2652 KB |
Output is correct |
4 |
Correct |
1 ms |
2780 KB |
Output is correct |
5 |
Correct |
1 ms |
2652 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
30 ms |
6992 KB |
Output is correct |
2 |
Correct |
24 ms |
5980 KB |
Output is correct |
3 |
Correct |
23 ms |
5724 KB |
Output is correct |
4 |
Correct |
25 ms |
6236 KB |
Output is correct |
5 |
Correct |
38 ms |
8028 KB |
Output is correct |
6 |
Correct |
28 ms |
9564 KB |
Output is correct |
7 |
Correct |
24 ms |
8284 KB |
Output is correct |
8 |
Correct |
28 ms |
8028 KB |
Output is correct |
9 |
Correct |
15 ms |
6164 KB |
Output is correct |
10 |
Correct |
28 ms |
9308 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
1 ms |
2652 KB |
Output is correct |
2 |
Correct |
1 ms |
2652 KB |
Output is correct |
3 |
Correct |
1 ms |
2652 KB |
Output is correct |
4 |
Correct |
1 ms |
2780 KB |
Output is correct |
5 |
Correct |
1 ms |
2652 KB |
Output is correct |
6 |
Correct |
2 ms |
2648 KB |
Output is correct |
7 |
Correct |
1 ms |
2652 KB |
Output is correct |
8 |
Correct |
1 ms |
2652 KB |
Output is correct |
9 |
Correct |
1 ms |
2652 KB |
Output is correct |
10 |
Correct |
1 ms |
2652 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
1 ms |
2652 KB |
Output is correct |
2 |
Correct |
1 ms |
2652 KB |
Output is correct |
3 |
Correct |
1 ms |
2652 KB |
Output is correct |
4 |
Correct |
1 ms |
2780 KB |
Output is correct |
5 |
Correct |
1 ms |
2652 KB |
Output is correct |
6 |
Correct |
30 ms |
6992 KB |
Output is correct |
7 |
Correct |
24 ms |
5980 KB |
Output is correct |
8 |
Correct |
23 ms |
5724 KB |
Output is correct |
9 |
Correct |
25 ms |
6236 KB |
Output is correct |
10 |
Correct |
38 ms |
8028 KB |
Output is correct |
11 |
Correct |
28 ms |
9564 KB |
Output is correct |
12 |
Correct |
24 ms |
8284 KB |
Output is correct |
13 |
Correct |
28 ms |
8028 KB |
Output is correct |
14 |
Correct |
15 ms |
6164 KB |
Output is correct |
15 |
Correct |
28 ms |
9308 KB |
Output is correct |
16 |
Correct |
2 ms |
2648 KB |
Output is correct |
17 |
Correct |
1 ms |
2652 KB |
Output is correct |
18 |
Correct |
1 ms |
2652 KB |
Output is correct |
19 |
Correct |
1 ms |
2652 KB |
Output is correct |
20 |
Correct |
1 ms |
2652 KB |
Output is correct |
21 |
Correct |
10 ms |
3932 KB |
Output is correct |
22 |
Correct |
9 ms |
4084 KB |
Output is correct |
23 |
Correct |
42 ms |
9672 KB |
Output is correct |
24 |
Correct |
29 ms |
7768 KB |
Output is correct |
25 |
Correct |
29 ms |
7604 KB |
Output is correct |
26 |
Correct |
18 ms |
5980 KB |
Output is correct |
27 |
Correct |
22 ms |
6492 KB |
Output is correct |
28 |
Correct |
30 ms |
7760 KB |
Output is correct |
29 |
Correct |
19 ms |
5980 KB |
Output is correct |
30 |
Correct |
56 ms |
10156 KB |
Output is correct |