# | Time | Username | Problem | Language | Result | Execution time | Memory |
---|---|---|---|---|---|---|---|
237209 | IgorI | Cat in a tree (BOI17_catinatree) | C++17 | 0 ms | 0 KiB |
This submission is migrated from previous version of oj.uz, which used different machine for grading. This submission may have different result if resubmitted.
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
const int N = 2000;
int n, d;
int dp[N][2000];
int p[N];
vector<int> graph[N];
void dfs(int v)
{
for (auto u : graph[v]) dfs(u);
dp[v][0] = 1;
for (auto u : graph[v]) dp[v][0] += dp[u][d - 1];
for (int j = 1; j <= d; j++)
{
int allow = d - j - 1;
int fl = 0;
if (allow * 2 + 2 < d)
{
allow = (d + 1) / 2 - 1;
fl = 1;
}
allow = max(allow, j - 1);
for (auto u : graph[v])
{
int res = dp[u][j - 1];
for (auto w : graph[v]) if (w != u)
res += dp[w][allow];
/*int delta = 0;
if (d % 2 == 1 && fl)
{
for (auto w : graph[v]) if (w != u) if (allow >= j && allow + allow + 1 <= d && allow + j <= d)
delta = max(delta, dp[w][allow - 1] - dp[w][allow]);
}*/
dp[v][j] = max(dp[v][j], res + delta);
}
}
for (int j = d - 1; j >= 0; j--) dp[v][j] = max(dp[v][j], dp[v][j + 1]);
}
signed main()
{
ios_base::sync_with_stdio(false);
cin.tie(0);
cout.tie(0);
cin >> n >> d;
if (d == 1) cout << n, exit(0);
for (int i = 1; i < n; i++)
{
cin >> p[i];
graph[p[i]].push_back(i);
}
dfs(0);
cout << dp[0][0];
}