fork download
copy 
  1. /// Author : Nguyễn Thái Sơn - Ti20 - THPT chuyên Lương Thế Vinh
  2.  
  3. #include<bits/stdc++.h>
  4. //#include <ext/pb_ds/assoc_container.hpp>
  5. //#include <ext/pb_ds/trie_policy.hpp>
  6. //#include <ext/rope>
  7.  
  8. //#pragma GCC optimize("Ofast")
  9. //#pragma GCC optimization("unroll-loops, no-stack-protector")
  10. //#pragma GCC target("avx,avx2,fma")
  11.  
  12. //using namespace std;
  13. //using namespace __gnu_pbds;
  14. //using namespace __gnu_cxx;
  15.  
  16. #define fi first
  17. #define se second
  18. #define TASK "test"
  19. #define pb push_back
  20. #define EL cout << endl
  21. #define Ti20_ntson int main()
  22. #define in(x) cout << x << endl
  23. #define all(x) (x).begin(),(x).end()
  24. #define getbit(x, i) (((x) >> (i)) & 1)
  25. #define cntbit(x) __builtin_popcount(x)
  26. #define FOR(i,l,r) for (int i = l; i <= r; i++)
  27. #define FORD(i,l,r) for (int i = l; i >= r; i--)
  28. #define Debug(a,n) for (int i = 1; i <= n; i++) cout << a[i] << " "; cout << endl
  29.  
  30. using namespace std;
  31.  
  32. typedef long long ll;
  33. typedef vector<int> vi;
  34. typedef pair<int,int> vii;
  35. typedef unsigned long long ull;
  36. typedef vector<vector<int>> vvi;
  37.  
  38. const int N = 1e5 + 5;
  39. const int oo = INT_MAX;
  40. const int mod = 1e9 + 7;
  41. const int d4x[4] = {-1, 0, 1, 0} , d4y[4] = {0, 1, 0, -1};
  42. const int d8x[8] = {-1, -1, 0, 1, 1, 1, 0, -1}, d8y[8] = {0, 1, 1, 1, 0, -1, -1, -1};
  43.  
  44. int n, a[N];
  45. ll Ans = 0;
  46. vector<vii> V;
  47.  
  48. inline void Read_Input() {
  49.     cin >> n;
  50.     FOR(i, 1, n) cin >> a[i];
  51.     FOR(i, 2, n) {
  52.         register int u, v;
  53.         cin >> u >> v;
  54.         V.push_back(vii(u, v));
  55.     }
  56.     sort(all(V), [&](vii u, vii v) {
  57.         return max(a[u.fi], a[u.se]) < max(a[v.fi], a[v.se]);
  58.     });
  59. }
  60.  
  61. struct DSU {
  62.     vector<int> par;
  63.     int mx[N];
  64.  
  65.     inline void init(int _n) {
  66.         par.resize(_n + 5, -1);
  67.         FOR(i, 1, _n)
  68.             mx[i] = a[i];
  69.     }
  70.  
  71.     inline int FIND(int u) {
  72.         return par[u] < 0 ? u : (par[u] = FIND(par[u]));
  73.     }
  74.  
  75.     inline void MERGE(int u, int v) {
  76.         u = FIND(u);
  77.         v = FIND(v);
  78.         if (u == v) return;
  79.         if (par[u] < par[v]) swap(u, v);
  80.         /// Gom 2 dinh lai
  81.         Ans += mx[u] + mx[v];
  82.  
  83.         /// Khi dua 2 thang ve cung 1 tplt
  84.  
  85.         mx[u] = max(mx[u], mx[v]);
  86.  
  87.         par[u] += par[v];
  88.         par[v] = u;
  89.     }
  90. }d;
  91.  
  92. inline void Solve() {
  93.     d.init(n);
  94.     for (auto[u, v] : V)
  95.         d.MERGE(u, v);
  96.     cout << Ans;
  97. }
  98.  
  99. Ti20_ntson {
  100. //    freopen(TASK".INP","r",stdin);
  101. //    freopen(TASK".OUT","w",stdout);
  102.     ios_base::sync_with_stdio(false); cin.tie(0); cout.tie(0);
  103.     int T = 1;
  104.     while (T -- ) {
  105.         Read_Input();
  106.         Solve();
  107.     }
  108. }
  109.  
Success #stdin #stdout 0.01s 5304KB
comments (?)
stdin
copy 
Standard input is empty
stdout
copy 
Standard output is empty
https://ideone.com/QpajQk
language:
C++14 (gcc 8.3)
created:
16 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!