/* Author : Tr3nity */
#include<bits/stdc++.h>
using namespace std;
#define ll long long int
#define mod1 (1000000000+7)
#define mod (998244353)
#define pb push_back
#define all(x) x.begin(), x.end()
#define mp make_pair
#define en cout << '\n'
const int N = 1e6+100, M = 1e5+10, K = 18;
struct dp{
int val, dist, next;
};
int n, d;
vector<int> g[N];
dp a[N];
void update(int v, int x, int dep, int nxt){
if(x > a[v].val){
a[v].val = x;
a[v].dist = dep;
a[v].next = nxt;
}else if(x == a[v].val && dep > a[v].dist){
a[v].dist = dep;
a[v].next = nxt;
}
}
void dfs(int v){
int sum = 0, small = 0, biggest_small = -1, smallest_big = d, next_smallest = d;
for(int u: g[v]){
dfs(u);
sum += a[u].val;
if(a[u].dist < (d+1)/2){
small++;
if(biggest_small == -1 || a[biggest_small].dist < a[u].dist){
biggest_small = u;
}
if(smallest_big > a[u].next)
next_smallest = smallest_big, smallest_big = a[u].next;
if(next_smallest > a[u].next)
next_smallest = a[u].next;
}else if(d % 2 == 0 && a[u].dist == d / 2){
biggest_small = u;
}
if((d+1)/2 <= a[u].dist){
if(smallest_big > a[u].dist)
next_smallest = smallest_big, smallest_big = a[u].dist;
if(next_smallest > a[u].next)
next_smallest = a[u].next;
}
}
if(g[v].size() == 0){
a[v].val = 1, a[v].dist = 1;
return;
}
bool put = min(next_smallest, smallest_big) == d;
update(v, sum - small + put, (put ? 0 : smallest_big), (put ? d : next_smallest));
if(biggest_small != -1)
update(v, sum - small + !(a[biggest_small].dist == d/2 && d%2==0), a[biggest_small].dist,
min({a[v].dist, a[biggest_small].next, smallest_big, next_smallest}));
a[v].dist++;
a[v].next++;
}
void solve(){
cin >> n >> d;
for(int i = 1; i <= n-1; ++i){
int x; cin >> x;
g[x].pb(i);
}
for(int i = 0; i < n; ++i) a[i].val = 0, a[i].dist = d, a[i].next = d;
dfs(0);
cout << a[0].val;
}
int main(){
cin.tie(0); ios::sync_with_stdio(0);
int tt = 1, aa;
// freopen("in.txt", "r", stdin);
// freopen("out.txt", "w", stdout);
// cin >> tt;aa=tt;
while(tt--){
solve();
}
cerr<<"time taken : "<<(float)clock()/CLOCKS_PER_SEC<<" seconds\n";
return 0;
}
Compilation message
catinatree.cpp: In function 'int main()':
catinatree.cpp:84:15: warning: unused variable 'aa' [-Wunused-variable]
84 | int tt = 1, aa;
| ^~
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
12 ms |
23764 KB |
Output is correct |
| 2 |
Incorrect |
12 ms |
23764 KB |
Output isn't correct |
| 3 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
12 ms |
23764 KB |
Output is correct |
| 2 |
Incorrect |
12 ms |
23764 KB |
Output isn't correct |
| 3 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
12 ms |
23764 KB |
Output is correct |
| 2 |
Incorrect |
12 ms |
23764 KB |
Output isn't correct |
| 3 |
Halted |
0 ms |
0 KB |
- |
