fork download
copy 
  1. /// Author : Nguyễn Thái Sơn - K18 - KHMT - UIT
  2. /// Training ICPC 2024
  3.  
  4. #include<bits/stdc++.h>
  5.  
  6. /// #pragma GCC optimize("O3,unroll-loops")
  7. /// #pragma GCC target("avx2,bmi,bmi2,lzcnt,popcnt")
  8.  
  9. #define fi first
  10. #define se second
  11. #define TASK "test"
  12. #define pb push_back
  13. #define EL cout << endl
  14. #define Ti20_ntson int main()
  15. #define in(x) cout << x << endl
  16. #define all(x) (x).begin(),(x).end()
  17. #define getbit(x, i) (((x) >> (i)) & 1)
  18. #define cntbit(x) __builtin_popcount(x)
  19. #define FOR(i,l,r) for (int i = l; i <= r; i++)
  20. #define FORD(i,l,r) for (int i = l; i >= r; i--)
  21. #define Debug(a,n) for (int i = 1; i <= n; i++) cout << a[i] << " "; cout << endl
  22.  
  23. using namespace std;
  24.  
  25. typedef long long ll;
  26. typedef vector<int> vi;
  27. typedef pair<int,int> vii;
  28. typedef unsigned long long ull;
  29. typedef vector<vector<int>> vvi;
  30. int fastMax(int x, int y) { return (((y-x)>>(32-1))&(x^y))^y; }
  31.  
  32. const int N = 5e5 + 5;
  33. const int oo = INT_MAX;
  34. const int mod = 1e9 + 7;
  35. const int d4x[4] = {-1, 0, 1, 0} , d4y[4] = {0, 1, 0, -1};
  36. const int d8x[8] = {-1, -1, 0, 1, 1, 1, 0, -1}, d8y[8] = {0, 1, 1, 1, 0, -1, -1, -1};
  37.  
  38. int n, a[N], u[N], v[N], dc[N], b[N];
  39. set<int> dd[N];
  40.  
  41. inline void Read_Input() {
  42.     cin >> n;
  43.     FOR(i, 1, n)
  44.         cin >> dc[i];
  45.     FOR(i, 1, n - 1) {
  46.         cin >> u[i] >> v[i];
  47.         dd[u[i]].insert(v[i]);
  48.         dd[v[i]].insert(u[i]);
  49.     }
  50. }
  51.  
  52. inline int find_mx(int u, int p) {
  53.     int Ans = u;
  54.     for (int v : dd[u])
  55.         if (v != p) {
  56.             int t = find_mx(v, u);
  57.             if (dc[t] > dc[Ans]) Ans = t;
  58.         }
  59.     return Ans;
  60. }
  61.  
  62. inline int Calc(int u) {
  63.     int Sum = 0;
  64.     int mx = find_mx(u, u);
  65.     /// Tim duoc dinh lon nhat
  66.     /// cat cac canh noi voi no
  67. //    cout << "CALC " << u << " " << mx << endl;
  68.     for (int v : dd[mx]) {
  69.         /// mx - v
  70.         Sum += dc[mx];
  71.         /// Xoa canh mx - v di
  72.         dd[v].erase(mx);
  73.         Sum += dc[find_mx(v, v)];
  74.         /// Tim dap an cho cay con moi duoc sinh ra
  75.         Sum += Calc(v);
  76.     }
  77.     dd[mx].clear();
  78.     return Sum;
  79. }
  80.  
  81. inline void Solve() {
  82.     cout << Calc(1);
  83. }
  84.  
  85. Ti20_ntson {
  86. //    freopen(TASK".INP","r",stdin);
  87. //    freopen(TASK".OUT","w",stdout);
  88.     ios_base::sync_with_stdio(false); cin.tie(0); cout.tie(0);
  89.     int T = 1;
  90. //    cin >> T;
  91.     while (T -- ) {
  92.         Read_Input();
  93.         Solve();
  94.     }
  95. }
  96.  
  97.  
  98.  
Success #stdin #stdout 0.01s 28880KB
comments (?)
stdin
copy 
Standard input is empty
stdout
copy 
Standard output is empty
https://ideone.com/3R67Q7
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!