| # | Time | Username | Problem | Language | Result | Execution time | Memory |
|---|---|---|---|---|---|---|---|
| 1334268 | ezzzay | Sjekira (COCI20_sjekira) | C11 | 0 ms | 0 KiB |
#include<bits/stdc++.h>
using namespace std;
#define ff first
#define ss second
#define pb push_back
#define int long long
const int N=3e5+5;
int sbtr[N];
int mx[N];
int par[N];
int find(int x){
if(par[x]==x)return x;
return par[x]=find(par[x]);
}
void merge(int x, int y){
if(sbtr[x]<sbtr[y]){
swap(x,y);
}
mx[x]=max(mx[x],mx[y]);
sbtr[x]+=sbtr[y];
par[y]=x;
}
signed main(){
int n;
cin>>n;
for(int i=1;i<=n;i++){
cin>>mx[i];
sbtr[i]=1;
par[i]=i;
}
set<vector<int>>st;
for(int i=1;i<n;i++){
int a,b;
cin>>a>>b;
st.insert({mx[a]+mx[b],a,b});
}
int ans=0;
while(!st.empty()){
auto v= *st.begin();
int w=v[0],a=v[1],b=v[2];
a=find(a),b=find(b);
if(mx[a]+mx[b]!=w){
st.erase(st.begin());
st.insert({mx[a]+mx[b],a,b});
continue;
}
ans+=w;
merge(a,b);
st.erase(st.begin());
}
cout<<ans;
}