#include <bits/stdc++.h>
using namespace std;
vector<int> adj[(int)2e5+7];
vector<int> dp[(int)2e5+7];
int N,D;
vector<int> smallMerge(vector<int> a, vector<int> b){
// for (int i=0; i<D; i++){
// cout<<a[i]<<' ';
// }
// cout<<'\n';
// for (int i=0; i<D; i++){
// cout<<b[i]<<' ';
// }
// cout<<'\n';
int tmp;
tmp = a[D-1];
for (int i=D-1; i>=1; i--) a[i] = a[i-1]; a[0] = tmp+1;
tmp = b[D-1];
for (int i=D-1; i>=1; i--) b[i] = b[i-1]; b[0] = tmp+1;
vector<int> maxa(D+1, 0), maxb(D+1, 0);
vector<int> res(D, 0);
for (int i=D-1; i>=0; i--) maxa[i] = max(maxa[i+1], a[i]);
for (int i=D-1; i>=0; i--) maxb[i] = max(maxb[i+1], b[i]);
for (int i=0; i<D; i++){
int ni = max(i, D-i);
res[i] = max(res[i], a[i] + maxb[ni]);
res[i] = max(res[i], b[i] + maxa[ni]);
}
// for (int i=0; i<D; i++){
// cout<<b[i]<<' ';
// }
// cout<<"\n\n\n";
return res;
}
int smallDFS(int i, int p){
int ans = 0;
dp[i].resize(D,0);
dp[i][0] = 1;
for (int c: adj[i]){
if (c==p) continue;
smallDFS(c, i);
dp[i] = smallMerge(dp[i], dp[c]);
}
for (int j=0; j<D; j++) ans = max(ans, dp[i][j]);
return ans;
}
int smallD(){
return smallDFS(0,0);
}
int main(){
cin>>N>>D; D++;
for (int i=1; i<N; i++){
int a; cin>>a;
adj[a].push_back(i); adj[i].push_back(a);
}
cout<<smallD()<<'\n';
}
Compilation message
catinatree.cpp: In function 'std::vector<int> smallMerge(std::vector<int>, std::vector<int>)':
catinatree.cpp:19:2: warning: this 'for' clause does not guard... [-Wmisleading-indentation]
19 | for (int i=D-1; i>=1; i--) a[i] = a[i-1]; a[0] = tmp+1;
| ^~~
catinatree.cpp:19:44: note: ...this statement, but the latter is misleadingly indented as if it were guarded by the 'for'
19 | for (int i=D-1; i>=1; i--) a[i] = a[i-1]; a[0] = tmp+1;
| ^
catinatree.cpp:21:2: warning: this 'for' clause does not guard... [-Wmisleading-indentation]
21 | for (int i=D-1; i>=1; i--) b[i] = b[i-1]; b[0] = tmp+1;
| ^~~
catinatree.cpp:21:44: note: ...this statement, but the latter is misleadingly indented as if it were guarded by the 'for'
21 | for (int i=D-1; i>=1; i--) b[i] = b[i-1]; b[0] = tmp+1;
| ^
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
3 ms |
9816 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
3 ms |
9816 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
3 ms |
9816 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
