Advertisement
Mehulcoder

1436D

Oct 26th, 2020 (edited)
68
0
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
C++ 1.57 KB | None | 0 0
  1. /*
  2. Author: Mehul Chaturvedi
  3. Talent is overrated
  4. */
  5.  
  6. #include <bits/stdc++.h>
  7. using namespace std;
  8.  
  9. using ll = long long;
  10. #define vll vector<long long>
  11. #define vvll vector<vector<ll>>
  12. #define rep(i, n) for (int i = 0, _n = (n); i < _n; i++)
  13. #define trav(a, x) for(auto& a : x)
  14.  
  15.  
  16. const ll N = 2e5 + 10;
  17.  
  18. ll n;
  19. vll edges[N];
  20. vll citizens;
  21.  
  22. ll ceel(ll a, ll b) {
  23.     if (!(a % b)) {
  24.         return a / b;
  25.     }
  26.     return a / b + 1;
  27. }
  28.  
  29. //Max, leaves, canTake
  30. vll dfs(ll root) {
  31.     if (!edges[root].size()) {
  32.         return {citizens[root], 1, 0};
  33.     }
  34.  
  35.     ll maxi = 0;
  36.     ll lv = 0;
  37.     vvll v;
  38.     trav(child, edges[root]) {
  39.         auto temp = dfs(child);
  40.         maxi = max(maxi, temp[0]);
  41.         lv += temp[1];
  42.         v.push_back(temp);
  43.     }
  44.  
  45.     ll curr = citizens[root];
  46.     ll canTake = 0;
  47.     trav(elem, v) {
  48.         canTake += elem[2] + (maxi - elem[0]) * elem[1];
  49.     }
  50.  
  51.     if (canTake >= curr) {
  52.         canTake = canTake - curr;
  53.         curr = 0;
  54.     } else {
  55.         curr -= canTake;
  56.         canTake = 0;
  57.     }
  58.     if (curr > 0) {
  59.         ll oldMaxi = maxi;
  60.         ll IncInAll = curr / lv;
  61.         ll incInFew = ceel(curr, lv);
  62.         maxi += incInFew;
  63.         ll cntMaxi = curr % lv;
  64.         if (!cntMaxi) cntMaxi = lv;
  65.  
  66.         canTake += lv - cntMaxi;
  67.     }
  68.  
  69.  
  70.     return {maxi, lv, canTake};
  71.  
  72. }
  73.  
  74. void solve() {
  75.     cin >> n;
  76.     citizens.resize(n, 0);
  77.     rep(i, n - 1) {
  78.         ll p; cin >> p;
  79.         p--;
  80.         edges[p].push_back(i + 1);
  81.     }
  82.  
  83.     rep(i, n) cin >> citizens[i];
  84.  
  85.     auto ans = dfs(0);
  86.     cout << ans[0] << '\n';
  87.     return;
  88. }
  89.  
  90. int main(int argc , char ** argv) {
  91.     ios_base::sync_with_stdio(false) ;
  92.     cin.tie(NULL) ;
  93.  
  94.     ll t = 1;
  95.  
  96.     while (t--) {
  97.         solve();
  98.     }
  99.  
  100.     return 0 ;
  101. }
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement