#include <bits/stdc++.h>
using namespace std;
int main() {
ios::sync_with_stdio(false);
cin.tie(nullptr);
int n, d;
cin >> n >> d;
vector<vector<int>> adj(n);
for (int i = 1, p; i < n; ++i) {
cin >> p;
adj[p].push_back(i);
}
if (d >= n) {
cout << "1\n";
return 0;
}
// dp[u][d] = in the subtree of u, nodes are at least d away from the root
auto dfs = [&](auto &&self, int u) -> vector<int> {
vector<int> ch_dp(n), dp(n);
int sum = 0;
for (int &i : adj[u]) {
vector<int> res = self(self, i);
sum += res[d - 1];
for (int d = 0; d < n; ++d) {
for (int l = 0; 2 * l <= d; ++l) {
dp[d] = max(dp[d], res[l] + ch_dp[d - l]);
}
}
for (int i = 0; i < n; ++i) {
ch_dp[i] += res[i];
}
}
dp[0] = max(dp[0], sum + 1);
return dp;
};
auto dp = dfs(dfs, 0);
cout << dp[0] << '\n';
}
| # | Verdict | Execution time | Memory | Grader output |
|---|
| Fetching results... |
| # | Verdict | Execution time | Memory | Grader output |
|---|
| Fetching results... |
| # | Verdict | Execution time | Memory | Grader output |
|---|
| Fetching results... |