#include <bits/stdc++.h>
#define fast ios_base::sync_with_stdio(0);cin.tie(NULL);cout.tie(NULL)
#define ll long long int
#define ld long double
using namespace std;
const int N = 1501;
const int MOD = 1e9 + 7;
vector<int> graph[N];
int n, k, a[N], dp[N][N];
void dfs(int node, int par){
dp[node][0] = a[node];
for(auto kk : graph[node]){
if(kk == par) continue;
dfs(kk, node);
}
for(int depth = 0; depth <= n; ++depth){
if(!depth){
for(auto kk : graph[node]){
if(kk == par) continue;
dp[node][depth] += dp[kk][max(0, k - depth - 1)];
}
continue;
}
for(auto kk : graph[node]){
if(kk == par) continue;
int cur = dp[kk][depth - 1];
for(auto j : graph[node]){
if(j == kk or j == par) continue;
cur += dp[j][max(k - depth - 1, depth - 1)];
}
dp[node][depth] = max(dp[node][depth], cur);
}
}
for(int depth = n; depth > 0; --depth)
dp[node][depth - 1] = max(dp[node][depth - 1] , dp[node][depth]);
}
void solve(){
cin >> n >> k;
for(int i = 1; i <= n; ++i)
a[i] = 1;
for(int i = 2; i <= n; ++i){
int p;
cin >> p;
++p;
graph[i].push_back(p);
graph[p].push_back(i);
}
// let dp[i][depth] be the max sum of subset of vertices that we can take from the subtree
// of v such that the minimum depth of a selected node is atleast depth.
dfs(1, 0);
cout << dp[1][0] << '\n';
}
int main(){
fast;
int t = 1;
// cin >> t;
while(t--)
solve();
return 0;
// you should actually read the stuff at the bottom
}
/* stuff you should look for
* int overflow, array bounds
* special cases (n=1?)
* do smth instead of nothing and stay organized
* WRITE STUFF DOWN
* DON'T GET STUCK ON ONE APPROACH
* Read other problems if stuck on this one.
*/
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
1 ms |
332 KB |
Output is correct |
2 |
Correct |
0 ms |
332 KB |
Output is correct |
3 |
Correct |
0 ms |
332 KB |
Output is correct |
4 |
Correct |
1 ms |
332 KB |
Output is correct |
5 |
Correct |
1 ms |
332 KB |
Output is correct |
6 |
Correct |
0 ms |
332 KB |
Output is correct |
7 |
Correct |
1 ms |
332 KB |
Output is correct |
8 |
Correct |
0 ms |
332 KB |
Output is correct |
9 |
Correct |
1 ms |
332 KB |
Output is correct |
10 |
Correct |
1 ms |
332 KB |
Output is correct |
11 |
Correct |
1 ms |
332 KB |
Output is correct |
12 |
Correct |
1 ms |
332 KB |
Output is correct |
13 |
Correct |
1 ms |
332 KB |
Output is correct |
14 |
Correct |
1 ms |
332 KB |
Output is correct |
15 |
Correct |
1 ms |
332 KB |
Output is correct |
16 |
Correct |
0 ms |
332 KB |
Output is correct |
17 |
Correct |
1 ms |
332 KB |
Output is correct |
18 |
Correct |
1 ms |
332 KB |
Output is correct |
19 |
Correct |
1 ms |
332 KB |
Output is correct |
20 |
Correct |
1 ms |
332 KB |
Output is correct |
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
1 ms |
332 KB |
Output is correct |
2 |
Correct |
0 ms |
332 KB |
Output is correct |
3 |
Correct |
0 ms |
332 KB |
Output is correct |
4 |
Correct |
1 ms |
332 KB |
Output is correct |
5 |
Correct |
1 ms |
332 KB |
Output is correct |
6 |
Correct |
0 ms |
332 KB |
Output is correct |
7 |
Correct |
1 ms |
332 KB |
Output is correct |
8 |
Correct |
0 ms |
332 KB |
Output is correct |
9 |
Correct |
1 ms |
332 KB |
Output is correct |
10 |
Correct |
1 ms |
332 KB |
Output is correct |
11 |
Correct |
1 ms |
332 KB |
Output is correct |
12 |
Correct |
1 ms |
332 KB |
Output is correct |
13 |
Correct |
1 ms |
332 KB |
Output is correct |
14 |
Correct |
1 ms |
332 KB |
Output is correct |
15 |
Correct |
1 ms |
332 KB |
Output is correct |
16 |
Correct |
0 ms |
332 KB |
Output is correct |
17 |
Correct |
1 ms |
332 KB |
Output is correct |
18 |
Correct |
1 ms |
332 KB |
Output is correct |
19 |
Correct |
1 ms |
332 KB |
Output is correct |
20 |
Correct |
1 ms |
332 KB |
Output is correct |
21 |
Correct |
20 ms |
9304 KB |
Output is correct |
22 |
Correct |
4 ms |
3276 KB |
Output is correct |
23 |
Correct |
4 ms |
3276 KB |
Output is correct |
24 |
Correct |
4 ms |
3276 KB |
Output is correct |
25 |
Correct |
14 ms |
6292 KB |
Output is correct |
26 |
Correct |
14 ms |
6220 KB |
Output is correct |
27 |
Correct |
15 ms |
6276 KB |
Output is correct |
28 |
Correct |
28 ms |
9208 KB |
Output is correct |
29 |
Correct |
28 ms |
9140 KB |
Output is correct |
30 |
Correct |
27 ms |
9184 KB |
Output is correct |
31 |
Correct |
27 ms |
9104 KB |
Output is correct |
32 |
Correct |
271 ms |
8932 KB |
Output is correct |
33 |
Correct |
279 ms |
9024 KB |
Output is correct |
34 |
Correct |
59 ms |
8620 KB |
Output is correct |
35 |
Correct |
55 ms |
8516 KB |
Output is correct |
36 |
Correct |
70 ms |
9208 KB |
Output is correct |
37 |
Correct |
66 ms |
9164 KB |
Output is correct |
38 |
Correct |
36 ms |
9172 KB |
Output is correct |
39 |
Correct |
36 ms |
9176 KB |
Output is correct |
40 |
Correct |
20 ms |
9252 KB |
Output is correct |
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
1 ms |
332 KB |
Output is correct |
2 |
Correct |
0 ms |
332 KB |
Output is correct |
3 |
Correct |
0 ms |
332 KB |
Output is correct |
4 |
Correct |
1 ms |
332 KB |
Output is correct |
5 |
Correct |
1 ms |
332 KB |
Output is correct |
6 |
Correct |
0 ms |
332 KB |
Output is correct |
7 |
Correct |
1 ms |
332 KB |
Output is correct |
8 |
Correct |
0 ms |
332 KB |
Output is correct |
9 |
Correct |
1 ms |
332 KB |
Output is correct |
10 |
Correct |
1 ms |
332 KB |
Output is correct |
11 |
Correct |
1 ms |
332 KB |
Output is correct |
12 |
Correct |
1 ms |
332 KB |
Output is correct |
13 |
Correct |
1 ms |
332 KB |
Output is correct |
14 |
Correct |
1 ms |
332 KB |
Output is correct |
15 |
Correct |
1 ms |
332 KB |
Output is correct |
16 |
Correct |
0 ms |
332 KB |
Output is correct |
17 |
Correct |
1 ms |
332 KB |
Output is correct |
18 |
Correct |
1 ms |
332 KB |
Output is correct |
19 |
Correct |
1 ms |
332 KB |
Output is correct |
20 |
Correct |
1 ms |
332 KB |
Output is correct |
21 |
Correct |
20 ms |
9304 KB |
Output is correct |
22 |
Correct |
4 ms |
3276 KB |
Output is correct |
23 |
Correct |
4 ms |
3276 KB |
Output is correct |
24 |
Correct |
4 ms |
3276 KB |
Output is correct |
25 |
Correct |
14 ms |
6292 KB |
Output is correct |
26 |
Correct |
14 ms |
6220 KB |
Output is correct |
27 |
Correct |
15 ms |
6276 KB |
Output is correct |
28 |
Correct |
28 ms |
9208 KB |
Output is correct |
29 |
Correct |
28 ms |
9140 KB |
Output is correct |
30 |
Correct |
27 ms |
9184 KB |
Output is correct |
31 |
Correct |
27 ms |
9104 KB |
Output is correct |
32 |
Correct |
271 ms |
8932 KB |
Output is correct |
33 |
Correct |
279 ms |
9024 KB |
Output is correct |
34 |
Correct |
59 ms |
8620 KB |
Output is correct |
35 |
Correct |
55 ms |
8516 KB |
Output is correct |
36 |
Correct |
70 ms |
9208 KB |
Output is correct |
37 |
Correct |
66 ms |
9164 KB |
Output is correct |
38 |
Correct |
36 ms |
9172 KB |
Output is correct |
39 |
Correct |
36 ms |
9176 KB |
Output is correct |
40 |
Correct |
20 ms |
9252 KB |
Output is correct |
41 |
Runtime error |
1 ms |
588 KB |
Execution killed with signal 11 |
42 |
Halted |
0 ms |
0 KB |
- |