Advertisement
Guest User

Untitled

a guest
Oct 18th, 2019
95
0
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
text 0.89 KB | None | 0 0
  1.  
  2.  
  3.  
  4. #include <bits/stdc++.h>
  5.  
  6. using namespace std;
  7. vector<vector<int>> g;
  8. vector<long long> dyn;
  9. vector<long long> max_children;
  10. vector<bool> used;
  11. int n;
  12. long long m = 0;
  13.  
  14. void f(int v) {
  15. used[v] = true;
  16. for (auto i: g[v]) {
  17. if (!used[i]) f(i);
  18. dyn[v] += max_children[i];
  19. max_children[v] += max(max_children[i], dyn[i]);
  20. }
  21.  
  22. m = max(dyn[v], m);
  23. }
  24.  
  25. int main()
  26. {
  27. ios_base::sync_with_stdio(0);
  28. cin.tie(0);
  29.  
  30. ofstream fout("select.out");
  31. ifstream fin("select.in");
  32.  
  33. int start;
  34.  
  35. fin >> n;
  36. g.resize(n);
  37. dyn.resize(n, 1);
  38. max_children.resize(n);
  39. used.resize(n+1, false);
  40. int t;
  41.  
  42. for (int i = 0; i < n; i++) {
  43. fin >> t;
  44. if (t!= 0) g[t-1].push_back(i);
  45. else start = i;
  46. }
  47.  
  48. f(start);
  49.  
  50. fout << max(max_children[start], dyn[start]);
  51.  
  52. return 0;
  53. }
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement