#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
const int N = 1e6 + 1,MOD = 1e9 + 7;
struct ans{
deque<int> dp;
int sz(){
return (int)dp.size();
}
ans():dp({1}){}
};
ans x[N];
int n,d;
vector<int> g[N];
void merge(ans &a,ans &b){
if(b.sz() > a.sz()){
swap(a,b);
}
vector<int> combined_dp = vector<int> (b.dp.begin(),b.dp.end());
for(int i = 0;i < (int)b.sz();i++){
int t = d - i;
if(t >= d){
if(t < a.sz()) combined_dp[i] = max(combined_dp[i],b.dp[i] + a.dp[t]);
if(t < b.sz()) combined_dp[i] = max(combined_dp[i],b.dp[t] + a.dp[i]);
}else{
combined_dp[i] = b.dp[i] + a.dp[i];
}
}
int mx = 0;
for(int i = b.sz() - 1;i >= 0;i--){
mx = max(mx,combined_dp[i]);
a.dp[i] = max(a.dp[i],mx);
}
}
ans& dfs(int v){
ans& f = x[v];
for(int to:g[v]){
ans &child = dfs(to);
child.dp.push_front(child.dp.front());
merge(f,child);
}
return f;
}
void test(){
cin >> n >> d;
for(int i = 2;i <= n;i++){
int x;
cin >> x;
++x;
g[x].push_back(i);
}
cout << dfs(1).dp[0];
}
int main(){
ios_base::sync_with_stdio(0);cin.tie(0);
int T = 1;
// cin >> T;
while(T--)
test();
}
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Runtime error |
227 ms |
524288 KB |
Execution killed with signal 9 |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Runtime error |
227 ms |
524288 KB |
Execution killed with signal 9 |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Runtime error |
227 ms |
524288 KB |
Execution killed with signal 9 |
| 2 |
Halted |
0 ms |
0 KB |
- |
