#include <bits/stdc++.h>
using namespace std;
#define rep(i, a, b) for (int i = a; i < b; ++i)
#define per(i, a, b) for (int i = b - 1; i >= a; --i)
#define trav(x, a) for (auto& x : a)
typedef pair<int, int> ii;
typedef long long ll;
typedef vector<int> vi;
typedef vector<ii> vii;
typedef vector<vi> vvi;
vi graph[1501];
int d, memo[1501][1501];
int dp(int u, int dist) {
int& ans = memo[u][dist];
if (ans != -1) return ans;
ans = 0;
if (!dist) {
ans = 1;
trav(v, graph[u]) ans += dp(v, d - 1);
}
int i = max(1, dist);
while (1) {
int j = d - i, sum = 0;
if (j < i) break;
trav(v, graph[u]) sum += dp(v, j - 1);
trav(v, graph[u]) ans = max(ans, sum - memo[v][j - 1] + dp(v, i - 1));
if (j < 2) break;
++i;
}
return ans;
}
int main() {
cin.tie(0)->sync_with_stdio(0);
memset(memo, -1, sizeof(memo));
int n, p;
cin >> n >> d;
d = min(d, n);
if (1500 < n) return 0;
rep(i, 1, n) {
cin >> p;
graph[p].push_back(i);
}
cout << dp(0, 0) << endl;
return 0;
}
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
5 ms |
9164 KB |
Output is correct |
2 |
Incorrect |
5 ms |
9164 KB |
Output isn't correct |
3 |
Halted |
0 ms |
0 KB |
- |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
5 ms |
9164 KB |
Output is correct |
2 |
Incorrect |
5 ms |
9164 KB |
Output isn't correct |
3 |
Halted |
0 ms |
0 KB |
- |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
5 ms |
9164 KB |
Output is correct |
2 |
Incorrect |
5 ms |
9164 KB |
Output isn't correct |
3 |
Halted |
0 ms |
0 KB |
- |