#include <iostream>
#include <vector>
#include <deque>
using namespace std;
const int NMAX = 2e5;
int N, D;
vector<int> g[NMAX + 5];
int depth[NMAX + 5];
deque<int> dp[NMAX + 5];
vector<int> sumD;
vector<int> maxForD;
void dfs(int node) {
if (g[node].empty()) {
dp[node].push_back(1);
return;
}
depth[node] = 1;
for (auto it : g[node]) {
dfs(it);
depth[node] = max(depth[node], 1 + depth[it]);
}
///GET DEEPEST CHILD
int deepestChild = -1;
for (auto it : g[node]) {
if (deepestChild == -1) {
deepestChild = it;
} else if (depth[it] > depth[deepestChild]) {
deepestChild = it;
}
}
///GET SECOND DEPTH
int secondDepth = 0;
for (auto it : g[node]) {
if (it != deepestChild) {
secondDepth = max(secondDepth, depth[it]);
}
}
///CALCULATE sumD and maxForD (up to secondDepth)
maxForD.resize(secondDepth + 2);
sumD.resize(secondDepth + 2);
for (int i = 0; i <= secondDepth + 1; i++)
sumD[i] = maxForD[i] = 0;
for (auto it : g[node]) {
int lim = min(D / 2, min(secondDepth + 1, depth[it] + 1));
for (int d = 1; d <= lim; d++) {
int f = 0;
if (depth[it] >= D - d - 1) {
f = dp[it][D - d - 1];
}
maxForD[d] = max(maxForD[d], dp[it][d - 1] - f);
sumD[d] += f;
}
}
///CALCULATE DP[node][0]
int sum = 1;
for (auto it : g[node]) {
if (depth[it] >= D - 1) {
sum += dp[it][D - 1];
}
}
///CALCULATE DP[node][d] for 2 * d >= D
swap(dp[node], dp[deepestChild]);
dp[node].push_front(sum);
for (auto it : g[node]) {
if (it != deepestChild) {
for (int d = 1; d <= min(D - 1, depth[it] + 1); d++)
dp[node][d] += dp[it][d - 1];
}
}
///CALCULATE DP[node][d] for 2 * d < D
for (int d = 1; d <= min(secondDepth + 1, D / 2); d++)
dp[node][d] = sumD[d] + maxForD[d];
///PROPAGATING DP[node][d] = max(DP[node][d], DP[node][d + 1])
for (int d = min(secondDepth, D - 2); d >= 0; d--)
dp[node][d] = max(dp[node][d], dp[node][d + 1]);
}
int main() {
cin >> N >> D;
for (int i = 1; i < N; i++) {
int x;
cin >> x;
g[x].push_back(i);
}
dfs(0);
cout << dp[0][0] << '\n';
return 0;
}
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
108 ms |
139628 KB |
Output is correct |
2 |
Correct |
106 ms |
139628 KB |
Output is correct |
3 |
Correct |
107 ms |
139628 KB |
Output is correct |
4 |
Correct |
106 ms |
139628 KB |
Output is correct |
5 |
Correct |
106 ms |
139628 KB |
Output is correct |
6 |
Correct |
106 ms |
139628 KB |
Output is correct |
7 |
Correct |
105 ms |
139628 KB |
Output is correct |
8 |
Correct |
106 ms |
139628 KB |
Output is correct |
9 |
Correct |
107 ms |
139628 KB |
Output is correct |
10 |
Correct |
105 ms |
139756 KB |
Output is correct |
11 |
Correct |
105 ms |
139720 KB |
Output is correct |
12 |
Correct |
109 ms |
139628 KB |
Output is correct |
13 |
Correct |
106 ms |
139628 KB |
Output is correct |
14 |
Correct |
107 ms |
139628 KB |
Output is correct |
15 |
Correct |
106 ms |
139756 KB |
Output is correct |
16 |
Correct |
109 ms |
139704 KB |
Output is correct |
17 |
Correct |
106 ms |
139628 KB |
Output is correct |
18 |
Correct |
107 ms |
139628 KB |
Output is correct |
19 |
Correct |
108 ms |
139756 KB |
Output is correct |
20 |
Correct |
106 ms |
139756 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
108 ms |
139628 KB |
Output is correct |
2 |
Correct |
106 ms |
139628 KB |
Output is correct |
3 |
Correct |
107 ms |
139628 KB |
Output is correct |
4 |
Correct |
106 ms |
139628 KB |
Output is correct |
5 |
Correct |
106 ms |
139628 KB |
Output is correct |
6 |
Correct |
106 ms |
139628 KB |
Output is correct |
7 |
Correct |
105 ms |
139628 KB |
Output is correct |
8 |
Correct |
106 ms |
139628 KB |
Output is correct |
9 |
Correct |
107 ms |
139628 KB |
Output is correct |
10 |
Correct |
105 ms |
139756 KB |
Output is correct |
11 |
Correct |
105 ms |
139720 KB |
Output is correct |
12 |
Correct |
109 ms |
139628 KB |
Output is correct |
13 |
Correct |
106 ms |
139628 KB |
Output is correct |
14 |
Correct |
107 ms |
139628 KB |
Output is correct |
15 |
Correct |
106 ms |
139756 KB |
Output is correct |
16 |
Correct |
109 ms |
139704 KB |
Output is correct |
17 |
Correct |
106 ms |
139628 KB |
Output is correct |
18 |
Correct |
107 ms |
139628 KB |
Output is correct |
19 |
Correct |
108 ms |
139756 KB |
Output is correct |
20 |
Correct |
106 ms |
139756 KB |
Output is correct |
21 |
Correct |
107 ms |
139884 KB |
Output is correct |
22 |
Correct |
106 ms |
139756 KB |
Output is correct |
23 |
Correct |
107 ms |
139756 KB |
Output is correct |
24 |
Correct |
107 ms |
139756 KB |
Output is correct |
25 |
Correct |
117 ms |
139884 KB |
Output is correct |
26 |
Correct |
117 ms |
139756 KB |
Output is correct |
27 |
Correct |
107 ms |
139756 KB |
Output is correct |
28 |
Correct |
115 ms |
139884 KB |
Output is correct |
29 |
Correct |
119 ms |
139884 KB |
Output is correct |
30 |
Correct |
114 ms |
139884 KB |
Output is correct |
31 |
Correct |
117 ms |
139884 KB |
Output is correct |
32 |
Correct |
112 ms |
139632 KB |
Output is correct |
33 |
Correct |
111 ms |
139628 KB |
Output is correct |
34 |
Correct |
108 ms |
139756 KB |
Output is correct |
35 |
Correct |
106 ms |
139756 KB |
Output is correct |
36 |
Correct |
109 ms |
139884 KB |
Output is correct |
37 |
Correct |
107 ms |
139628 KB |
Output is correct |
38 |
Correct |
106 ms |
139756 KB |
Output is correct |
39 |
Correct |
108 ms |
139884 KB |
Output is correct |
40 |
Correct |
107 ms |
139884 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
108 ms |
139628 KB |
Output is correct |
2 |
Correct |
106 ms |
139628 KB |
Output is correct |
3 |
Correct |
107 ms |
139628 KB |
Output is correct |
4 |
Correct |
106 ms |
139628 KB |
Output is correct |
5 |
Correct |
106 ms |
139628 KB |
Output is correct |
6 |
Correct |
106 ms |
139628 KB |
Output is correct |
7 |
Correct |
105 ms |
139628 KB |
Output is correct |
8 |
Correct |
106 ms |
139628 KB |
Output is correct |
9 |
Correct |
107 ms |
139628 KB |
Output is correct |
10 |
Correct |
105 ms |
139756 KB |
Output is correct |
11 |
Correct |
105 ms |
139720 KB |
Output is correct |
12 |
Correct |
109 ms |
139628 KB |
Output is correct |
13 |
Correct |
106 ms |
139628 KB |
Output is correct |
14 |
Correct |
107 ms |
139628 KB |
Output is correct |
15 |
Correct |
106 ms |
139756 KB |
Output is correct |
16 |
Correct |
109 ms |
139704 KB |
Output is correct |
17 |
Correct |
106 ms |
139628 KB |
Output is correct |
18 |
Correct |
107 ms |
139628 KB |
Output is correct |
19 |
Correct |
108 ms |
139756 KB |
Output is correct |
20 |
Correct |
106 ms |
139756 KB |
Output is correct |
21 |
Correct |
107 ms |
139884 KB |
Output is correct |
22 |
Correct |
106 ms |
139756 KB |
Output is correct |
23 |
Correct |
107 ms |
139756 KB |
Output is correct |
24 |
Correct |
107 ms |
139756 KB |
Output is correct |
25 |
Correct |
117 ms |
139884 KB |
Output is correct |
26 |
Correct |
117 ms |
139756 KB |
Output is correct |
27 |
Correct |
107 ms |
139756 KB |
Output is correct |
28 |
Correct |
115 ms |
139884 KB |
Output is correct |
29 |
Correct |
119 ms |
139884 KB |
Output is correct |
30 |
Correct |
114 ms |
139884 KB |
Output is correct |
31 |
Correct |
117 ms |
139884 KB |
Output is correct |
32 |
Correct |
112 ms |
139632 KB |
Output is correct |
33 |
Correct |
111 ms |
139628 KB |
Output is correct |
34 |
Correct |
108 ms |
139756 KB |
Output is correct |
35 |
Correct |
106 ms |
139756 KB |
Output is correct |
36 |
Correct |
109 ms |
139884 KB |
Output is correct |
37 |
Correct |
107 ms |
139628 KB |
Output is correct |
38 |
Correct |
106 ms |
139756 KB |
Output is correct |
39 |
Correct |
108 ms |
139884 KB |
Output is correct |
40 |
Correct |
107 ms |
139884 KB |
Output is correct |
41 |
Correct |
259 ms |
171752 KB |
Output is correct |
42 |
Correct |
222 ms |
153452 KB |
Output is correct |
43 |
Correct |
226 ms |
153580 KB |
Output is correct |
44 |
Correct |
228 ms |
153452 KB |
Output is correct |
45 |
Correct |
226 ms |
153708 KB |
Output is correct |
46 |
Correct |
355 ms |
167572 KB |
Output is correct |
47 |
Correct |
353 ms |
167404 KB |
Output is correct |
48 |
Correct |
358 ms |
167532 KB |
Output is correct |
49 |
Correct |
356 ms |
167276 KB |
Output is correct |
50 |
Correct |
162 ms |
140908 KB |
Output is correct |
51 |
Correct |
162 ms |
140908 KB |
Output is correct |
52 |
Correct |
162 ms |
141036 KB |
Output is correct |
53 |
Correct |
208 ms |
141676 KB |
Output is correct |
54 |
Correct |
209 ms |
141776 KB |
Output is correct |
55 |
Correct |
213 ms |
141676 KB |
Output is correct |
56 |
Correct |
107 ms |
139884 KB |
Output is correct |
57 |
Correct |
129 ms |
143468 KB |
Output is correct |
58 |
Correct |
171 ms |
156396 KB |
Output is correct |
59 |
Correct |
248 ms |
158956 KB |
Output is correct |
60 |
Correct |
245 ms |
167272 KB |
Output is correct |
61 |
Correct |
251 ms |
153196 KB |
Output is correct |