/* 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, BS = -1, SB = d, NS = d;
for(int u: g[v]){
dfs(u);
sum += a[u].val;
if(a[u].dist < (d+1)/2){
small++;
if(BS == -1 || a[BS].dist < a[u].dist){
BS = u;
}
if(SB > a[u].next)
NS = SB, SB = a[u].next;
else if(NS > a[u].next)
NS = a[u].next;
}else if(d % 2 == 0 && a[u].dist == d / 2){
BS = u;
}
if((d+1)/2 <= a[u].dist){
if(SB > a[u].next)
NS = SB, SB = a[u].next;
else if(NS > a[u].next)
NS = a[u].next;
if(SB > a[u].dist)
NS = SB, SB = a[u].dist;
else if(NS > a[u].dist)
NS = a[u].dist;
}
}
if(g[v].size() == 0){
a[v].val = 1, a[v].dist = 1;
return;
}
bool put = SB == d;
update(v, sum - small + put, (put ? 0 : SB), (put ? d : NS));
if(BS != -1 && a[BS].dist + SB >= d){
if(d % 2 == 0 && a[BS].dist == d/2){
update(v, sum - small, d/2, NS);
}else{
update(v, sum - small + 1, a[BS].dist, SB);
}
}
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:93:15: warning: unused variable 'aa' [-Wunused-variable]
93 | int tt = 1, aa;
| ^~
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
13 ms |
23764 KB |
Output is correct |
2 |
Correct |
12 ms |
23764 KB |
Output is correct |
3 |
Correct |
13 ms |
23764 KB |
Output is correct |
4 |
Correct |
10 ms |
23764 KB |
Output is correct |
5 |
Correct |
10 ms |
23720 KB |
Output is correct |
6 |
Correct |
11 ms |
23816 KB |
Output is correct |
7 |
Correct |
11 ms |
23696 KB |
Output is correct |
8 |
Correct |
11 ms |
23764 KB |
Output is correct |
9 |
Correct |
11 ms |
23764 KB |
Output is correct |
10 |
Correct |
11 ms |
23704 KB |
Output is correct |
11 |
Correct |
11 ms |
23764 KB |
Output is correct |
12 |
Correct |
14 ms |
23764 KB |
Output is correct |
13 |
Correct |
11 ms |
23756 KB |
Output is correct |
14 |
Correct |
11 ms |
23764 KB |
Output is correct |
15 |
Correct |
10 ms |
23764 KB |
Output is correct |
16 |
Correct |
12 ms |
23820 KB |
Output is correct |
17 |
Correct |
11 ms |
23764 KB |
Output is correct |
18 |
Correct |
13 ms |
23764 KB |
Output is correct |
19 |
Correct |
11 ms |
23764 KB |
Output is correct |
20 |
Correct |
11 ms |
23764 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
13 ms |
23764 KB |
Output is correct |
2 |
Correct |
12 ms |
23764 KB |
Output is correct |
3 |
Correct |
13 ms |
23764 KB |
Output is correct |
4 |
Correct |
10 ms |
23764 KB |
Output is correct |
5 |
Correct |
10 ms |
23720 KB |
Output is correct |
6 |
Correct |
11 ms |
23816 KB |
Output is correct |
7 |
Correct |
11 ms |
23696 KB |
Output is correct |
8 |
Correct |
11 ms |
23764 KB |
Output is correct |
9 |
Correct |
11 ms |
23764 KB |
Output is correct |
10 |
Correct |
11 ms |
23704 KB |
Output is correct |
11 |
Correct |
11 ms |
23764 KB |
Output is correct |
12 |
Correct |
14 ms |
23764 KB |
Output is correct |
13 |
Correct |
11 ms |
23756 KB |
Output is correct |
14 |
Correct |
11 ms |
23764 KB |
Output is correct |
15 |
Correct |
10 ms |
23764 KB |
Output is correct |
16 |
Correct |
12 ms |
23820 KB |
Output is correct |
17 |
Correct |
11 ms |
23764 KB |
Output is correct |
18 |
Correct |
13 ms |
23764 KB |
Output is correct |
19 |
Correct |
11 ms |
23764 KB |
Output is correct |
20 |
Correct |
11 ms |
23764 KB |
Output is correct |
21 |
Correct |
11 ms |
24148 KB |
Output is correct |
22 |
Correct |
11 ms |
23728 KB |
Output is correct |
23 |
Correct |
11 ms |
23764 KB |
Output is correct |
24 |
Correct |
11 ms |
23812 KB |
Output is correct |
25 |
Correct |
14 ms |
23776 KB |
Output is correct |
26 |
Correct |
11 ms |
23836 KB |
Output is correct |
27 |
Correct |
11 ms |
23812 KB |
Output is correct |
28 |
Correct |
11 ms |
23764 KB |
Output is correct |
29 |
Correct |
11 ms |
23776 KB |
Output is correct |
30 |
Correct |
15 ms |
23828 KB |
Output is correct |
31 |
Correct |
11 ms |
23828 KB |
Output is correct |
32 |
Correct |
11 ms |
23764 KB |
Output is correct |
33 |
Correct |
11 ms |
23820 KB |
Output is correct |
34 |
Correct |
11 ms |
23820 KB |
Output is correct |
35 |
Correct |
12 ms |
23812 KB |
Output is correct |
36 |
Correct |
12 ms |
23764 KB |
Output is correct |
37 |
Correct |
11 ms |
23764 KB |
Output is correct |
38 |
Correct |
11 ms |
23856 KB |
Output is correct |
39 |
Correct |
12 ms |
23824 KB |
Output is correct |
40 |
Correct |
11 ms |
23956 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
13 ms |
23764 KB |
Output is correct |
2 |
Correct |
12 ms |
23764 KB |
Output is correct |
3 |
Correct |
13 ms |
23764 KB |
Output is correct |
4 |
Correct |
10 ms |
23764 KB |
Output is correct |
5 |
Correct |
10 ms |
23720 KB |
Output is correct |
6 |
Correct |
11 ms |
23816 KB |
Output is correct |
7 |
Correct |
11 ms |
23696 KB |
Output is correct |
8 |
Correct |
11 ms |
23764 KB |
Output is correct |
9 |
Correct |
11 ms |
23764 KB |
Output is correct |
10 |
Correct |
11 ms |
23704 KB |
Output is correct |
11 |
Correct |
11 ms |
23764 KB |
Output is correct |
12 |
Correct |
14 ms |
23764 KB |
Output is correct |
13 |
Correct |
11 ms |
23756 KB |
Output is correct |
14 |
Correct |
11 ms |
23764 KB |
Output is correct |
15 |
Correct |
10 ms |
23764 KB |
Output is correct |
16 |
Correct |
12 ms |
23820 KB |
Output is correct |
17 |
Correct |
11 ms |
23764 KB |
Output is correct |
18 |
Correct |
13 ms |
23764 KB |
Output is correct |
19 |
Correct |
11 ms |
23764 KB |
Output is correct |
20 |
Correct |
11 ms |
23764 KB |
Output is correct |
21 |
Correct |
11 ms |
24148 KB |
Output is correct |
22 |
Correct |
11 ms |
23728 KB |
Output is correct |
23 |
Correct |
11 ms |
23764 KB |
Output is correct |
24 |
Correct |
11 ms |
23812 KB |
Output is correct |
25 |
Correct |
14 ms |
23776 KB |
Output is correct |
26 |
Correct |
11 ms |
23836 KB |
Output is correct |
27 |
Correct |
11 ms |
23812 KB |
Output is correct |
28 |
Correct |
11 ms |
23764 KB |
Output is correct |
29 |
Correct |
11 ms |
23776 KB |
Output is correct |
30 |
Correct |
15 ms |
23828 KB |
Output is correct |
31 |
Correct |
11 ms |
23828 KB |
Output is correct |
32 |
Correct |
11 ms |
23764 KB |
Output is correct |
33 |
Correct |
11 ms |
23820 KB |
Output is correct |
34 |
Correct |
11 ms |
23820 KB |
Output is correct |
35 |
Correct |
12 ms |
23812 KB |
Output is correct |
36 |
Correct |
12 ms |
23764 KB |
Output is correct |
37 |
Correct |
11 ms |
23764 KB |
Output is correct |
38 |
Correct |
11 ms |
23856 KB |
Output is correct |
39 |
Correct |
12 ms |
23824 KB |
Output is correct |
40 |
Correct |
11 ms |
23956 KB |
Output is correct |
41 |
Correct |
33 ms |
30784 KB |
Output is correct |
42 |
Correct |
27 ms |
27108 KB |
Output is correct |
43 |
Correct |
27 ms |
27084 KB |
Output is correct |
44 |
Correct |
28 ms |
27148 KB |
Output is correct |
45 |
Correct |
33 ms |
27272 KB |
Output is correct |
46 |
Correct |
46 ms |
30476 KB |
Output is correct |
47 |
Correct |
47 ms |
30540 KB |
Output is correct |
48 |
Correct |
47 ms |
30476 KB |
Output is correct |
49 |
Correct |
48 ms |
30492 KB |
Output is correct |
50 |
Correct |
20 ms |
25880 KB |
Output is correct |
51 |
Correct |
19 ms |
25880 KB |
Output is correct |
52 |
Correct |
19 ms |
25884 KB |
Output is correct |
53 |
Correct |
35 ms |
28036 KB |
Output is correct |
54 |
Correct |
28 ms |
28012 KB |
Output is correct |
55 |
Correct |
35 ms |
28008 KB |
Output is correct |
56 |
Correct |
11 ms |
23892 KB |
Output is correct |
57 |
Correct |
16 ms |
26580 KB |
Output is correct |
58 |
Correct |
26 ms |
36812 KB |
Output is correct |
59 |
Correct |
42 ms |
39880 KB |
Output is correct |
60 |
Correct |
35 ms |
31304 KB |
Output is correct |
61 |
Correct |
38 ms |
31052 KB |
Output is correct |