fork download
copy 
  1. #include <bits/stdc++.h>
  2. using namespace std;
  3.  
  4. #define maxn 100010
  5. #define ena long long
  6.  
  7. ena n, ans;
  8. ena c[maxn], cost[maxn], par[maxn], rankk[maxn];
  9.  
  10. vector <tuple<ena,ena,ena>> a;
  11.  
  12. ena root(ena u)
  13. {
  14.     return (u == par[u]) ? u : par[u] = root(par[u]);
  15. }
  16.  
  17. int main()
  18. {
  19.     freopen("gold.inp","r",stdin);
  20.     freopen("gold.out","w",stdout);
  21.     a.push_back(make_tuple(0,0,0));
  22.  
  23.     cin >> n;
  24.     for(ena i=1; i<=n; i++)
  25.     {
  26.         cin >> c[i];
  27.         cost[i] = c[i];
  28.         par[i] = i;
  29.     }
  30.  
  31.     for(ena i=1; i<=n-1; i++)
  32.     {
  33.         ena u, v;
  34.         cin >> u >> v;
  35.         a.push_back(make_tuple(max(c[u], c[v]), u, v));
  36.     }
  37.  
  38.     sort(a.begin(), a.end());
  39.  
  40.     for(ena i=1; i<=n-1; i++)
  41.     {
  42.         ena u = get<1>(a[i]);
  43.         ena v = get<2>(a[i]);
  44.         ena ru = root(u);
  45.         ena rv = root(v);
  46.  
  47.         if(ru != rv)
  48.         {
  49.             if(rankk[ru] < rankk[rv]) swap(ru, rv);
  50.             if(rankk[ru] == rankk[rv]) rankk[ru]++;
  51.  
  52.             ans += cost[ru] + cost[rv];
  53.             cost[ru] = max(cost[ru], cost[rv]);
  54.             par[rv] = ru;
  55.         }
  56.     }
  57.     cout << ans;
  58.     return 0;
  59. }
  60.  
Success #stdin #stdout 0.01s 5280KB
comments (?)
stdin
copy 
Standard input is empty
stdout
copy 
Standard output is empty
https://ideone.com/zSQrAP
gold_NhutTri
language:
C++14 (gcc 8.3)
created:
2 days ago
visibility:
public

Share or Embed source code

Discover > Sphere Engine API

The brand new service which powers Ideone!

Discover > IDE Widget

Widget for compiling and running the source code in a web browser!