#include <bits/stdc++.h>
#define fi first
#define se second
#define pb push_back
#define sz(a) (int)a.size()
#define all(a) a.begin(),a.end()
#define rep(i,n) for(int i=0;i<n;i++)
#define crep(i,x,n) for(int i=x;i<n;i++)
#define drep(i,n) for(int i=n-1;i>=0;i--)
#define vec(...) vector<__VA_ARGS__>
#define _3HaBFkZ ios_base::sync_with_stdio(false),cin.tie(0),cout.tie(0)
using namespace std;
typedef long long ll;
typedef long double ld;
using pii=pair<int,int>;
using vi=vector<int>;
struct dsu{
int n,size_;
vector<int> par,siz,maxima;
dsu(int m,vi a){
init(m,a);
}
void init(int m,vi a){
n=m;
size_=m;
par.resize(n,0);
siz.resize(n,0);
maxima.resize(n,0);
for(int i=0;i<n;i++){
par[i]=i;
siz[i]=1;
maxima[i]=a[i];
}
}
void merge(int x,int y,int type=0){
int a=parent(x),b=parent(y);
if(a==b) return;
size_--;
if(siz[a]>siz[b]) {
siz[a]+=siz[b];
par[b]=a;
maxima[a]=max(maxima[a],maxima[b]);
}else{
siz[b]+=siz[a];
par[a]=b;
maxima[b]=max(maxima[b],maxima[a]);
}
}
int parent(int x){
return par[x]==x?x:parent(par[x]);
}
bool same(int x, int y){
return parent(x)==parent(y);
}
int size(){
return size_;
}
};
int main(){
_3HaBFkZ;
int n;
cin>>n;
vi a(n);
rep(i,n){
cin>>a[i];
}
// vec(vi) adj(n);
vec(pii) edges;
rep(i,n-1){
int u,v;
cin>>u>>v;
u--,v--;
edges.pb({u,v});
}
// priority_queue<pii> pq;
// rep(i,n){
// pq.push({-a[i],i});
// }
dsu uf(n,a);
ll ans=0;
vi usd(n-1,0);
while(true){
int mn=1e9,j=-1;
rep(i,n-1){
if(usd[i]) continue;
int u=edges[i].fi,v=edges[i].se;
int par1=uf.parent(u),par2=uf.parent(v);
int cost=uf.maxima[par1]+uf.maxima[par2];
if(cost<mn){
mn=cost;
j=i;
}
}
if(j==-1) break;
usd[j]=1;
int u=edges[j].fi,v=edges[j].se;
ans+=mn;
uf.merge(u,v);
}
// while(sz(pq)>1){
// pii top=pq.top();
// pq.pop();
// pii netop=pq.top();
// pq.pop();
// if(uf.same(top.se,netop.se)) continue;
// cout<<top.se<<" "<<netop.se<<"\n";
// ans+=-top.fi-netop.fi;
// uf.merge(top.se,netop.se);
// int par=uf.parent(top.se);
// pq.push({-uf.maxima[par],par});
// }
cout<<ans<<"\n";
//
return 0;
}
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
0 ms |
208 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Execution timed out |
1091 ms |
4512 KB |
Time limit exceeded |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
0 ms |
208 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
0 ms |
208 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
