#include <bits/stdc++.h>
using namespace std;
#define int long long
#ifdef LOCAL
#include "algo/debug.h"
#else
#define debug(...) 42
#endif
#define all(a) (a).begin(), (a).end()
#define rep(i, n) for (int i = 0; i < (n); ++i)
#define reps(i, s, n) for (int i = s; i < (n); ++i)
#define pb push_back
#define sz(a) (int) (a.size())
void solve() {
int n, d;
cin >> n >> d;
if (d > n - 1) {
cout << 1;
return;
}
if (d == 0) {
cout << n;
return;
}
vector<int> p(n);
vector<vector<int>> g(n);
reps(i, 1, n) {
cin >> p[i];
g[p[i]].push_back(i);
}
vector<vector<int>> dp(n, vector<int> (n));
function<void(int)> dfs = [&] (int v) {
for (auto &u : g[v]) {
dfs(u);
}
debug(v);
// v is off
for (int dist = 1; dist <= d; dist++) {
debug(dist);
for (auto &u : g[v]) {
int tr = dp[u][dist - 1];
int other = max(dist, d - dist);
for (auto &w : g[v]) {
if (w != u) {
tr += dp[w][other - 1];
}
}
dp[v][dist] = max(dp[v][dist], tr);
}
}
// v is on
int tr = 0;
for (auto &u : g[v]) {
tr += dp[u][d - 1];
}
debug(v, tr);
dp[v][0] = max(dp[v][0], 1 + tr);
for (int dist = d - 1; dist >= 0; dist--) {
dp[v][dist] = max(dp[v][dist], dp[v][dist + 1]);
}
// reps(dist, 1, n) {
// dp[v][dist] = max(dp[v][dist], dp[v][dist - 1]);
// }
debug(v, dp[v]);
};
dfs(0);
int res = 0;
rep(i, n) {
rep(dist, d + 1) {
res = max(res, dp[i][dist]);
}
}
cout << res;
}
signed main() {
ios_base::sync_with_stdio(0);
cin.tie(0);
solve();
return 0;
}
Compilation message
catinatree.cpp: In lambda function:
catinatree.cpp:9:20: warning: statement has no effect [-Wunused-value]
9 | #define debug(...) 42
| ^~
catinatree.cpp:44:5: note: in expansion of macro 'debug'
44 | debug(v);
| ^~~~~
catinatree.cpp:9:20: warning: statement has no effect [-Wunused-value]
9 | #define debug(...) 42
| ^~
catinatree.cpp:47:7: note: in expansion of macro 'debug'
47 | debug(dist);
| ^~~~~
catinatree.cpp:9:20: warning: statement has no effect [-Wunused-value]
9 | #define debug(...) 42
| ^~
catinatree.cpp:65:5: note: in expansion of macro 'debug'
65 | debug(v, tr);
| ^~~~~
catinatree.cpp:9:20: warning: statement has no effect [-Wunused-value]
9 | #define debug(...) 42
| ^~
catinatree.cpp:73:5: note: in expansion of macro 'debug'
73 | debug(v, dp[v]);
| ^~~~~
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
1 ms |
212 KB |
Output is correct |
2 |
Correct |
1 ms |
212 KB |
Output is correct |
3 |
Correct |
0 ms |
212 KB |
Output is correct |
4 |
Correct |
0 ms |
212 KB |
Output is correct |
5 |
Correct |
0 ms |
212 KB |
Output is correct |
6 |
Correct |
1 ms |
212 KB |
Output is correct |
7 |
Correct |
0 ms |
212 KB |
Output is correct |
8 |
Correct |
0 ms |
212 KB |
Output is correct |
9 |
Correct |
0 ms |
212 KB |
Output is correct |
10 |
Correct |
0 ms |
212 KB |
Output is correct |
11 |
Correct |
0 ms |
212 KB |
Output is correct |
12 |
Correct |
0 ms |
212 KB |
Output is correct |
13 |
Correct |
0 ms |
212 KB |
Output is correct |
14 |
Correct |
0 ms |
212 KB |
Output is correct |
15 |
Correct |
0 ms |
212 KB |
Output is correct |
16 |
Correct |
0 ms |
212 KB |
Output is correct |
17 |
Correct |
0 ms |
212 KB |
Output is correct |
18 |
Correct |
0 ms |
212 KB |
Output is correct |
19 |
Correct |
0 ms |
212 KB |
Output is correct |
20 |
Correct |
0 ms |
212 KB |
Output is correct |
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
1 ms |
212 KB |
Output is correct |
2 |
Correct |
1 ms |
212 KB |
Output is correct |
3 |
Correct |
0 ms |
212 KB |
Output is correct |
4 |
Correct |
0 ms |
212 KB |
Output is correct |
5 |
Correct |
0 ms |
212 KB |
Output is correct |
6 |
Correct |
1 ms |
212 KB |
Output is correct |
7 |
Correct |
0 ms |
212 KB |
Output is correct |
8 |
Correct |
0 ms |
212 KB |
Output is correct |
9 |
Correct |
0 ms |
212 KB |
Output is correct |
10 |
Correct |
0 ms |
212 KB |
Output is correct |
11 |
Correct |
0 ms |
212 KB |
Output is correct |
12 |
Correct |
0 ms |
212 KB |
Output is correct |
13 |
Correct |
0 ms |
212 KB |
Output is correct |
14 |
Correct |
0 ms |
212 KB |
Output is correct |
15 |
Correct |
0 ms |
212 KB |
Output is correct |
16 |
Correct |
0 ms |
212 KB |
Output is correct |
17 |
Correct |
0 ms |
212 KB |
Output is correct |
18 |
Correct |
0 ms |
212 KB |
Output is correct |
19 |
Correct |
0 ms |
212 KB |
Output is correct |
20 |
Correct |
0 ms |
212 KB |
Output is correct |
21 |
Correct |
20 ms |
18240 KB |
Output is correct |
22 |
Correct |
2 ms |
2236 KB |
Output is correct |
23 |
Correct |
1 ms |
2240 KB |
Output is correct |
24 |
Correct |
1 ms |
2260 KB |
Output is correct |
25 |
Correct |
5 ms |
8124 KB |
Output is correct |
26 |
Correct |
4 ms |
8132 KB |
Output is correct |
27 |
Correct |
4 ms |
8148 KB |
Output is correct |
28 |
Correct |
9 ms |
18016 KB |
Output is correct |
29 |
Correct |
10 ms |
18032 KB |
Output is correct |
30 |
Correct |
10 ms |
18060 KB |
Output is correct |
31 |
Correct |
10 ms |
18004 KB |
Output is correct |
32 |
Correct |
11 ms |
17364 KB |
Output is correct |
33 |
Correct |
10 ms |
17364 KB |
Output is correct |
34 |
Correct |
8 ms |
15700 KB |
Output is correct |
35 |
Correct |
8 ms |
15676 KB |
Output is correct |
36 |
Correct |
9 ms |
18044 KB |
Output is correct |
37 |
Correct |
9 ms |
17984 KB |
Output is correct |
38 |
Correct |
10 ms |
18004 KB |
Output is correct |
39 |
Correct |
10 ms |
18028 KB |
Output is correct |
40 |
Correct |
9 ms |
18260 KB |
Output is correct |
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
1 ms |
212 KB |
Output is correct |
2 |
Correct |
1 ms |
212 KB |
Output is correct |
3 |
Correct |
0 ms |
212 KB |
Output is correct |
4 |
Correct |
0 ms |
212 KB |
Output is correct |
5 |
Correct |
0 ms |
212 KB |
Output is correct |
6 |
Correct |
1 ms |
212 KB |
Output is correct |
7 |
Correct |
0 ms |
212 KB |
Output is correct |
8 |
Correct |
0 ms |
212 KB |
Output is correct |
9 |
Correct |
0 ms |
212 KB |
Output is correct |
10 |
Correct |
0 ms |
212 KB |
Output is correct |
11 |
Correct |
0 ms |
212 KB |
Output is correct |
12 |
Correct |
0 ms |
212 KB |
Output is correct |
13 |
Correct |
0 ms |
212 KB |
Output is correct |
14 |
Correct |
0 ms |
212 KB |
Output is correct |
15 |
Correct |
0 ms |
212 KB |
Output is correct |
16 |
Correct |
0 ms |
212 KB |
Output is correct |
17 |
Correct |
0 ms |
212 KB |
Output is correct |
18 |
Correct |
0 ms |
212 KB |
Output is correct |
19 |
Correct |
0 ms |
212 KB |
Output is correct |
20 |
Correct |
0 ms |
212 KB |
Output is correct |
21 |
Correct |
20 ms |
18240 KB |
Output is correct |
22 |
Correct |
2 ms |
2236 KB |
Output is correct |
23 |
Correct |
1 ms |
2240 KB |
Output is correct |
24 |
Correct |
1 ms |
2260 KB |
Output is correct |
25 |
Correct |
5 ms |
8124 KB |
Output is correct |
26 |
Correct |
4 ms |
8132 KB |
Output is correct |
27 |
Correct |
4 ms |
8148 KB |
Output is correct |
28 |
Correct |
9 ms |
18016 KB |
Output is correct |
29 |
Correct |
10 ms |
18032 KB |
Output is correct |
30 |
Correct |
10 ms |
18060 KB |
Output is correct |
31 |
Correct |
10 ms |
18004 KB |
Output is correct |
32 |
Correct |
11 ms |
17364 KB |
Output is correct |
33 |
Correct |
10 ms |
17364 KB |
Output is correct |
34 |
Correct |
8 ms |
15700 KB |
Output is correct |
35 |
Correct |
8 ms |
15676 KB |
Output is correct |
36 |
Correct |
9 ms |
18044 KB |
Output is correct |
37 |
Correct |
9 ms |
17984 KB |
Output is correct |
38 |
Correct |
10 ms |
18004 KB |
Output is correct |
39 |
Correct |
10 ms |
18028 KB |
Output is correct |
40 |
Correct |
9 ms |
18260 KB |
Output is correct |
41 |
Runtime error |
208 ms |
524288 KB |
Execution killed with signal 9 |
42 |
Halted |
0 ms |
0 KB |
- |