// Bismi ALlah
#include "bits/stdc++.h"
using namespace std;
#define int long long
int dp[1501][1501];
signed main () {
int n, d;
cin >> n >> d;
vector <int> g[n];
for(int i= 0; i < n; i ++) {
for(int j = 0; j< d; j ++) dp[i][j] = -1e9;
}
function <void(int,int)> dfs=[&](int v, int p) {
vector <int> child;
for(auto u : g[v]) {
if(u == p) continue;
dfs(u, v);
child.push_back(u);
}
if(child.size() == 0) {
dp[v][0] = 1;
return;
}
dp[v][0] = 1;
for(auto i : child) {
dp[v][0] += max(0LL, dp[i][d-1]);
}
for(int whichDist = 1; whichDist < d; whichDist ++) {
for(auto which : child) {
int sum = dp[which][whichDist-1];
if(child.size() == 2) {
for(auto other : child) {
if(other == which) continue;
sum += dp[other][d-whichDist-1];
}
}else {
for(auto other : child) {
if(other == which) continue;
sum += dp[other][max(d-whichDist-1, (d + 1) / 2 - 1)];
}
}
dp[v][whichDist] = max(dp[v][whichDist], sum);
}
}
};
for(int i = 1; i < n; i ++) {
int p;
cin >> p;
g[i].push_back(p);
g[p].push_back(i);
}
dfs(0, -1);
int ans = -1e9;
for(int i = 0; i < d; i ++) ans = max(ans, dp[0][i]);
/* for(int i = 0; i < n; i ++) {
for(int j = 0; j < d; j ++) {
cout << i << " " << j << " " << dp[i][j] << "\n";
}
}*/
cout << ans;
return 0;
}
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
0 ms |
348 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
0 ms |
348 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
0 ms |
348 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
