Advertisement
Josif_tepe

Untitled

Jul 1st, 2023
769
0
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
C++ 1.18 KB | None | 0 0
  1. #include <iostream>
  2. #include <vector>
  3. #include <bits/stdc++.h>
  4. using namespace std;
  5. const int maxn = 3e5 + 10;
  6. vector<int> graph[maxn];
  7. int rating[maxn];
  8. int parent[maxn];
  9. int dp[maxn];
  10. int dfs(int node) {
  11.     if(dp[node] != -1) {
  12.         return dp[node];
  13.     }
  14.    
  15.     int taken = rating[node];
  16.     for(int i = 0; i < (int) graph[node].size(); i++) {
  17.         int neighbour = graph[node][i];
  18.         for(int j = 0; j < (int) graph[neighbour].size(); j++) {
  19.             int neighbour_of_neighbour = graph[neighbour][j];
  20.             taken += dfs(neighbour_of_neighbour);
  21.         }
  22.     }
  23.     int not_taken = 0;
  24.     for(int i = 0; i < (int) graph[node].size(); i++) {
  25.         int neighbour = graph[node][i];
  26.         not_taken += dfs(neighbour);
  27.     }
  28.     return dp[node] = max(taken, not_taken);
  29. }
  30. int main() {
  31.     ios_base::sync_with_stdio(false);
  32.     memset(dp, -1, sizeof dp);
  33.     int n;
  34.     cin >> n;
  35.     cin >> rating[0];
  36.     for(int i = 1; i < n; i++) {
  37.         int p;
  38.         cin >> rating[i] >> p;
  39.         parent[i] = p;
  40.         graph[p].push_back(i);
  41.        
  42.     }
  43.     cout << dfs(0) << endl;
  44.    return 0;
  45. }
  46. /*
  47.  7
  48.  1 2
  49.  1 3
  50.  2 4
  51.  2 5
  52.  3 6
  53.  3 7
  54.  **/
  55.  
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement