#include<algorithm>
#include<cstdio>
int read(){
int ch=getchar(),num=0;
while(ch<48||ch>57)ch=getchar();
while(ch>=48&&ch<=57)num=(num<<3)+(num<<1)+(ch^48),ch=getchar();
return num;
}
const int maxn=100005;
int n,total,head[maxn],to[maxn<<1],next[maxn<<1];
void add(int u,int v){
to[++total]=v;
next[total]=head[u];
head[u]=total;
}
struct Node{
int t,id;
}node[maxn];
bool operator<(Node a,Node b){
return a.t==b.t?a.id<b.id:a.t<b.t;
}
int fa[maxn],max[maxn];
void clear(){
for(int i=1;i<=n;i++)fa[i]=i,max[i]=node[i].t;
}
int find(int x){
return x==fa[x]?x:fa[x]=find(fa[x]);
}
void merge(int x,int y){
x=find(x),y=find(y);
max[y]=max[x]>max[y]?max[x]:max[y];
fa[x]=y;
}
int rank[maxn];
long long answer;
int main(){
n=read();
for(int i=1;i<=n;i++)node[i]=Node{read(),i};
int u,v;
for(int i=1;i<n;i++){
u=read(),v=read();
add(u,v);
add(v,u);
}
clear();
std::sort(node+1,node+n+1);
for(int i=1;i<=n;i++)rank[node[i].id]=i;
for(int i=1;i<=n;i++){
u=node[i].id;
for(int j=head[u];j;j=next[j]){
v=to[j];
if(rank[u]>rank[v])answer+=max[find(u)]+max[find(v)],merge(v,u);
}
}
printf("%lld",answer);
return 0;
}
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
1 ms |
2396 KB |
Output is correct |
2 |
Correct |
0 ms |
2396 KB |
Output is correct |
3 |
Correct |
0 ms |
2396 KB |
Output is correct |
4 |
Correct |
0 ms |
2396 KB |
Output is correct |
5 |
Correct |
0 ms |
348 KB |
Output is correct |
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
15 ms |
5824 KB |
Output is correct |
2 |
Correct |
11 ms |
4720 KB |
Output is correct |
3 |
Correct |
12 ms |
4696 KB |
Output is correct |
4 |
Correct |
12 ms |
4824 KB |
Output is correct |
5 |
Correct |
19 ms |
6228 KB |
Output is correct |
6 |
Correct |
11 ms |
6740 KB |
Output is correct |
7 |
Correct |
9 ms |
5972 KB |
Output is correct |
8 |
Correct |
9 ms |
5756 KB |
Output is correct |
9 |
Correct |
6 ms |
4696 KB |
Output is correct |
10 |
Correct |
11 ms |
6740 KB |
Output is correct |
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
1 ms |
2396 KB |
Output is correct |
2 |
Correct |
0 ms |
2396 KB |
Output is correct |
3 |
Correct |
0 ms |
2396 KB |
Output is correct |
4 |
Correct |
0 ms |
2396 KB |
Output is correct |
5 |
Correct |
0 ms |
348 KB |
Output is correct |
6 |
Correct |
1 ms |
2392 KB |
Output is correct |
7 |
Correct |
0 ms |
2396 KB |
Output is correct |
8 |
Correct |
1 ms |
2396 KB |
Output is correct |
9 |
Correct |
1 ms |
2396 KB |
Output is correct |
10 |
Correct |
1 ms |
2396 KB |
Output is correct |
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
1 ms |
2396 KB |
Output is correct |
2 |
Correct |
0 ms |
2396 KB |
Output is correct |
3 |
Correct |
0 ms |
2396 KB |
Output is correct |
4 |
Correct |
0 ms |
2396 KB |
Output is correct |
5 |
Correct |
0 ms |
348 KB |
Output is correct |
6 |
Correct |
15 ms |
5824 KB |
Output is correct |
7 |
Correct |
11 ms |
4720 KB |
Output is correct |
8 |
Correct |
12 ms |
4696 KB |
Output is correct |
9 |
Correct |
12 ms |
4824 KB |
Output is correct |
10 |
Correct |
19 ms |
6228 KB |
Output is correct |
11 |
Correct |
11 ms |
6740 KB |
Output is correct |
12 |
Correct |
9 ms |
5972 KB |
Output is correct |
13 |
Correct |
9 ms |
5756 KB |
Output is correct |
14 |
Correct |
6 ms |
4696 KB |
Output is correct |
15 |
Correct |
11 ms |
6740 KB |
Output is correct |
16 |
Correct |
1 ms |
2392 KB |
Output is correct |
17 |
Correct |
0 ms |
2396 KB |
Output is correct |
18 |
Correct |
1 ms |
2396 KB |
Output is correct |
19 |
Correct |
1 ms |
2396 KB |
Output is correct |
20 |
Correct |
1 ms |
2396 KB |
Output is correct |
21 |
Correct |
5 ms |
3420 KB |
Output is correct |
22 |
Correct |
4 ms |
3164 KB |
Output is correct |
23 |
Correct |
21 ms |
5996 KB |
Output is correct |
24 |
Correct |
14 ms |
4956 KB |
Output is correct |
25 |
Correct |
15 ms |
4760 KB |
Output is correct |
26 |
Correct |
9 ms |
4188 KB |
Output is correct |
27 |
Correct |
11 ms |
4292 KB |
Output is correct |
28 |
Correct |
20 ms |
4844 KB |
Output is correct |
29 |
Correct |
11 ms |
3932 KB |
Output is correct |
30 |
Correct |
22 ms |
6236 KB |
Output is correct |