#include <bits/stdc++.h>
using namespace std;
#define fast ios_base::sync_with_stdio(false);cin.tie(NULL);cout.tie(NULL);
#define filetest freopen("debug.INP","r",stdin);freopen("debug.OUT","w",stdout);
#define file freopen("debug.INP","r",stdin);freopen("debug.OUT","w",stdout);
#define pii pair<int,int>
#define ll long long
const int N=1e5+6;
int p[N], d[N],s[N];
vector <pii> e;
bool cmp(const pii& a, const pii& b) {
int x = max(d[a.first], d[a.second]);
int y = max(d[b.first], d[b.second]);
return x<y;
}
int fset(int v)
{
if (v== p[v]) return v;
return p[v]=fset(p[v]);
}
ll temp=0;
void uset(int a,int b)
{
//int b=a-1;
//if (a>b) swap(a,b);
a = fset(a);
b = fset(b);
if (a!=b)
{
temp+=s[a]+s[b];
s[b]=max(s[b],s[a]);
p[a]=b;
}
}
int main(){
fast
int n;
cin >> n;
for (int i = 1; i <= n; i++)
{
cin >> d[i];
s[i]=d[i];
p[i]=i;
}
n--;
while (n--)
{
int x,y;
cin >> x >> y;
e.push_back(pii(x,y));
}
sort(e.begin(), e.end(), cmp);
for (auto i : e)
{
uset(i.first,i.second);
}
cout << temp<< " ";
}
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
1 ms |
212 KB |
Output is correct |
2 |
Correct |
1 ms |
212 KB |
Output is correct |
3 |
Correct |
1 ms |
212 KB |
Output is correct |
4 |
Correct |
1 ms |
212 KB |
Output is correct |
5 |
Correct |
1 ms |
340 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
35 ms |
4072 KB |
Output is correct |
2 |
Correct |
26 ms |
2880 KB |
Output is correct |
3 |
Correct |
24 ms |
2800 KB |
Output is correct |
4 |
Correct |
29 ms |
3576 KB |
Output is correct |
5 |
Correct |
44 ms |
4520 KB |
Output is correct |
6 |
Correct |
45 ms |
5068 KB |
Output is correct |
7 |
Correct |
38 ms |
4268 KB |
Output is correct |
8 |
Correct |
36 ms |
4044 KB |
Output is correct |
9 |
Correct |
23 ms |
2888 KB |
Output is correct |
10 |
Correct |
41 ms |
4912 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
1 ms |
212 KB |
Output is correct |
2 |
Correct |
1 ms |
212 KB |
Output is correct |
3 |
Correct |
1 ms |
212 KB |
Output is correct |
4 |
Correct |
1 ms |
212 KB |
Output is correct |
5 |
Correct |
1 ms |
340 KB |
Output is correct |
6 |
Correct |
1 ms |
340 KB |
Output is correct |
7 |
Correct |
1 ms |
340 KB |
Output is correct |
8 |
Correct |
1 ms |
340 KB |
Output is correct |
9 |
Correct |
1 ms |
340 KB |
Output is correct |
10 |
Correct |
1 ms |
336 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
1 ms |
212 KB |
Output is correct |
2 |
Correct |
1 ms |
212 KB |
Output is correct |
3 |
Correct |
1 ms |
212 KB |
Output is correct |
4 |
Correct |
1 ms |
212 KB |
Output is correct |
5 |
Correct |
1 ms |
340 KB |
Output is correct |
6 |
Correct |
35 ms |
4072 KB |
Output is correct |
7 |
Correct |
26 ms |
2880 KB |
Output is correct |
8 |
Correct |
24 ms |
2800 KB |
Output is correct |
9 |
Correct |
29 ms |
3576 KB |
Output is correct |
10 |
Correct |
44 ms |
4520 KB |
Output is correct |
11 |
Correct |
45 ms |
5068 KB |
Output is correct |
12 |
Correct |
38 ms |
4268 KB |
Output is correct |
13 |
Correct |
36 ms |
4044 KB |
Output is correct |
14 |
Correct |
23 ms |
2888 KB |
Output is correct |
15 |
Correct |
41 ms |
4912 KB |
Output is correct |
16 |
Correct |
1 ms |
340 KB |
Output is correct |
17 |
Correct |
1 ms |
340 KB |
Output is correct |
18 |
Correct |
1 ms |
340 KB |
Output is correct |
19 |
Correct |
1 ms |
340 KB |
Output is correct |
20 |
Correct |
1 ms |
336 KB |
Output is correct |
21 |
Correct |
12 ms |
1452 KB |
Output is correct |
22 |
Correct |
9 ms |
1240 KB |
Output is correct |
23 |
Correct |
43 ms |
4400 KB |
Output is correct |
24 |
Correct |
33 ms |
3644 KB |
Output is correct |
25 |
Correct |
30 ms |
3564 KB |
Output is correct |
26 |
Correct |
21 ms |
2368 KB |
Output is correct |
27 |
Correct |
23 ms |
2516 KB |
Output is correct |
28 |
Correct |
27 ms |
3412 KB |
Output is correct |
29 |
Correct |
19 ms |
2264 KB |
Output is correct |
30 |
Correct |
45 ms |
4468 KB |
Output is correct |