Advertisement
Guest User

Untitled

a guest
Dec 17th, 2017
59
0
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
C++ 0.71 KB | None | 0 0
  1. #include <bits/stdc++.h>
  2.  
  3. using namespace std;
  4.  
  5.  
  6. int const inf = 1e9;
  7. int const maxN = 200;
  8.  
  9. vector <int> dp(maxN, inf);
  10. vector <int> children[maxN];
  11.  
  12.  
  13. int solve(int v) {
  14.     int s1 = 1;
  15.     int s2 = 0;
  16.     if (dp[v] == inf) {
  17.         if (children[v].empty()){
  18.             dp[v] = 1;
  19.         }
  20.         else {
  21.            
  22.             for (int u : children[v]){
  23.                 for (int w : children[u]) {
  24.                     s1 += solve(w);
  25.                 }
  26.             }
  27.             for (int u : children[v]) {
  28.                 s2 += solve(u);
  29.             }
  30.         }
  31.         dp[v] = max(s1, s2);
  32.     }
  33.     return dp[v];
  34. }
  35.  
  36. int main() {
  37.     int n;
  38.     cin >> n;
  39.     int root = 0;
  40.     for (int i = 1; i <= n; ++i) {
  41.         int p;
  42.         cin >> p;
  43.         if (p == 0) {
  44.             root = i;
  45.         }
  46.         else {
  47.             children[p].push_back(i);
  48.         }
  49.     }
  50.     cout << solve(root);
  51. }
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement