fork download
  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
stdin
Standard input is empty
stdout
Standard output is empty