DuongNhi99

Summax1

Dec 10th, 2020
99
0
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
C++ 0.90 KB | None | 0 0
  1. #include<bits/stdc++.h>
  2. #define ll long long
  3. using namespace std;
  4.  
  5. const int N = 200005;
  6.  
  7. int n;
  8. ll a[N];
  9. vector<ll> adj[N];
  10.  
  11. ll dp[N];
  12.  
  13. void DFS(int u, int parent) {
  14.     dp[u] = a[u];
  15.  
  16.     for(int v : adj[u]) {
  17.         if(v != parent) {
  18.         DFS(v, u);
  19.         dp[u] = max(dp[v] + a[u], dp[u]);
  20.         }
  21.     }
  22. }
  23.  
  24. int main() {
  25.     //freopen("in.txt", "r", stdin);
  26.     //freopen("Summax1.inp", "r", stdin);
  27.     //freopen("Summax1.out","w",stdout);
  28.     ios_base::sync_with_stdio(false);
  29.     cin.tie(0), cout.tie(0);
  30.  
  31.     cin >> n;
  32.     for(int i = 1; i <= n; i++)
  33.         cin >> a[i];
  34.     for(int i = 1; i <= n; i++) {
  35.         int u; cin >> u;
  36.         if(u == 0) continue;
  37.  
  38.         adj[u].push_back(i);
  39.         adj[i].push_back(u);
  40.     }
  41.     DFS(1, 0);
  42.  
  43.     cout << dp[1] << '\n';
  44.  
  45.     return 0;
  46. }
  47. /*
  48. 14
  49. 3 2 1 10 1 3 9 1 5 3 4 5 9 8
  50. 0 1 1 1 2 2 3 4 4 4 5 5 7 7
  51. ->22
  52. */
  53.  
Advertisement
Add Comment
Please, Sign In to add comment