Advertisement
Not a member of Pastebin yet?
Sign Up,
it unlocks many cool features!
- #include <bits/stdc++.h>
- using namespace std;
- vector<vector<int>> g;
- vector<long long> dyn;
- vector<long long> max_children;
- vector<bool> used;
- int n;
- long long m = 0;
- void f(int v) {
- used[v] = true;
- for (auto i: g[v]) {
- if (!used[i]) f(i);
- dyn[v] += max_children[i];
- max_children[v] += max(max_children[i], dyn[i]);
- }
- m = max(dyn[v], m);
- }
- int main()
- {
- ios_base::sync_with_stdio(0);
- cin.tie(0);
- ofstream fout("select.out");
- ifstream fin("select.in");
- int start;
- fin >> n;
- g.resize(n);
- dyn.resize(n, 1);
- max_children.resize(n);
- used.resize(n+1, false);
- int t;
- for (int i = 0; i < n; i++) {
- fin >> t;
- if (t!= 0) g[t-1].push_back(i);
- else start = i;
- }
- f(start);
- fout << max(max_children[start], dyn[start]);
- return 0;
- }
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement