Advertisement
DobriyKrot

11A

Dec 25th, 2022
75
0
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
C++ 0.83 KB | None | 0 0
  1. #include <iostream>
  2. #include <vector>
  3. #include <unordered_map>
  4.  
  5. using namespace std;
  6.  
  7. const int INF = 1e9 + 1;
  8.  
  9. vector<int> g[100];
  10. int pr[100];
  11. int q[100];
  12. int dp[100][2];
  13.  
  14. void dfs(int ver) {
  15.     dp[ver][0] = 0;
  16.     dp[ver][1] = q[ver];
  17.     for (const auto& i : g[ver]) {
  18.         if (i != pr[ver]) {
  19.             dfs(i);
  20.             dp[ver][0] += max(dp[i][0], dp[i][1]);
  21.             dp[ver][1] += dp[i][0];
  22.         }
  23.     }
  24. }
  25.  
  26. int main() {
  27.     ios_base::sync_with_stdio(false);
  28.     cin.tie(nullptr);
  29.     int n;
  30.     cin >> n;
  31.     int root = 0;
  32.     for (int i = 0; i < n; ++i) {
  33.         cin >> pr[i] >> q[i];
  34.         --pr[i];
  35.         if (pr[i] == -1) {
  36.             root = i;
  37.         } else {
  38.             g[pr[i]].emplace_back(i);
  39.         }
  40.     }
  41.     dfs(root);
  42.     cout << max(dp[root][0], dp[root][1]);
  43. }
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement