Not a member of Pastebin yet?
Sign Up,
it unlocks many cool features!
- #include <bits/stdc++.h>
- using namespace std;
- const int MAXN = 1e5 + 10;
- vector<int> grafo[MAXN];
- int dp[MAXN][5], dp2[MAXN][5][5];
- void dfs(int v)
- {
- for (int i = 0; i <= 3; i++) for (int j = 0; j <= 1; j++) dp2[0][i][j] = -1e9;
- dp2[0][0][0] = 0;
- for (int i = 0; i < grafo[v].size(); i++)
- {
- int viz = grafo[v][i];
- dfs(viz);
- dp[v][2] += dp[viz][0];
- dp[v][0] = max(dp[v][0], dp[viz][1]+1);
- }
- for (int i = 0; i < grafo[v].size(); i++)
- {
- int viz = grafo[v][i];
- for (int q2 = 2; q2 > 0; q2--)
- {
- dp2[i+1][q2][1] = max(dp2[i][q2][1] + dp[viz][0], max(dp2[i][q2-1][1] + dp[viz][2], dp2[i][q2][0] + dp[viz][3]));
- dp2[i+1][q2][0] = max(dp2[i][q2][0] + dp[viz][0], dp2[i][q2-1][0] + dp[viz][2]);
- }
- dp2[i+1][0][1] = max(dp2[i][0][1] + dp[viz][0], dp2[i][0][0] + dp[viz][3]);
- dp2[i+1][0][0] = dp2[i][0][0] + dp[viz][0];
- }
- dp[v][1] = dp2[grafo[v].size()][2][1];
- dp[v][3] = dp2[grafo[v].size()][2][0];
- dp[v][0] = max(dp[v][0], dp[v][2]);
- }
- int main()
- {
- ios_base::sync_with_stdio(false);
- cin.tie(NULL);
- int N;
- cin >> N;
- for (int i = 2; i <= N; i++)
- {
- int X;
- cin >> X;
- grafo[X].push_back(i);
- }
- for (int i = 2; i <= N; i++) if (grafo[i].size() == 1) {dp[i][0] = 0; dp[i][1] = -1e9; dp[i][2] = 0; dp[i][3] = -1e9;}
- dfs(1);
- int resp = 0;
- //resp = dp[1][0];
- for (auto viz : grafo[1]) resp += dp[viz][0];
- cout << resp << '\n';
- }
Add Comment
Please, Sign In to add comment
