#include <bits/stdc++.h>
/*
#include <ext/pb_ds/assoc_container.hpp>
#include <ext/pb_ds/tree_policy.hpp>
*/
using namespace std;
// using namespace __gnu_pbds;
using namespace chrono;
// mt19937 rng((int) std::chrono::steady_clock::now().time_since_epoch().count());
/*
template <class T> using ordered_set = tree <T, null_type, less <T>, rb_tree_tag, tree_order_statistics_node_update>;
*/
//***************** CONSTANTS *****************
const int MXN = 200000;
//***************** GLOBAL VARIABLES *****************
vector<int> g[MXN];
int ans = 0;
int N, D, d[MXN];
//***************** AUXILIARY STRUCTS *****************
//***************** MAIN BODY *****************
int dfs(int u, int p){
vector<int> t = {0};
ans++;
for(int v : g[u]) if(v != p){
t.push_back(dfs(v, u) + 1);
}
sort(t.begin(), t.end());
for(int i = t.size() - 1; i >= 1; --i){
if(t[i] + t[i - 1] < D){
ans -= i;
return t[i];
}
}
return t[0];
}
void solve(){
cin >> N >> D;
for(int i = 1; i < N; i++){
int x;
cin >> x;
g[x].push_back(i);
}
dfs(0, 0);
cout << ans << '\n';
}
//***************** *****************
int32_t main(){
ios_base::sync_with_stdio(NULL);
cin.tie(NULL);
#ifdef LOCAL
auto begin = high_resolution_clock::now();
#endif
int tc = 1;
// cin >> tc;
for (int t = 0; t < tc; t++)
solve();
#ifdef LOCAL
auto end = high_resolution_clock::now();
cout << fixed << setprecision(4);
cout << "Execution Time: " << duration_cast<duration<double>>(end - begin).count() << "seconds" << endl;
#endif
return 0;
}
/*
If code gives a WA, check for the following :
1. I/O format
2. Are you clearing all global variables in between tests if multitests are a thing
3. Can you definitively prove the logic
4. If the code gives an inexplicable TLE, and you are sure you have the best possible complexity,
use faster io
*/
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
3 ms |
4940 KB |
Output is correct |
2 |
Correct |
4 ms |
4940 KB |
Output is correct |
3 |
Correct |
3 ms |
4940 KB |
Output is correct |
4 |
Correct |
4 ms |
4940 KB |
Output is correct |
5 |
Correct |
4 ms |
4940 KB |
Output is correct |
6 |
Correct |
3 ms |
4940 KB |
Output is correct |
7 |
Correct |
3 ms |
4940 KB |
Output is correct |
8 |
Correct |
3 ms |
4940 KB |
Output is correct |
9 |
Correct |
3 ms |
4940 KB |
Output is correct |
10 |
Correct |
3 ms |
4940 KB |
Output is correct |
11 |
Correct |
3 ms |
4940 KB |
Output is correct |
12 |
Correct |
3 ms |
4940 KB |
Output is correct |
13 |
Correct |
3 ms |
5012 KB |
Output is correct |
14 |
Correct |
3 ms |
5016 KB |
Output is correct |
15 |
Correct |
3 ms |
4940 KB |
Output is correct |
16 |
Correct |
3 ms |
4940 KB |
Output is correct |
17 |
Correct |
3 ms |
4940 KB |
Output is correct |
18 |
Correct |
4 ms |
4940 KB |
Output is correct |
19 |
Correct |
3 ms |
4940 KB |
Output is correct |
20 |
Correct |
3 ms |
4940 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
3 ms |
4940 KB |
Output is correct |
2 |
Correct |
4 ms |
4940 KB |
Output is correct |
3 |
Correct |
3 ms |
4940 KB |
Output is correct |
4 |
Correct |
4 ms |
4940 KB |
Output is correct |
5 |
Correct |
4 ms |
4940 KB |
Output is correct |
6 |
Correct |
3 ms |
4940 KB |
Output is correct |
7 |
Correct |
3 ms |
4940 KB |
Output is correct |
8 |
Correct |
3 ms |
4940 KB |
Output is correct |
9 |
Correct |
3 ms |
4940 KB |
Output is correct |
10 |
Correct |
3 ms |
4940 KB |
Output is correct |
11 |
Correct |
3 ms |
4940 KB |
Output is correct |
12 |
Correct |
3 ms |
4940 KB |
Output is correct |
13 |
Correct |
3 ms |
5012 KB |
Output is correct |
14 |
Correct |
3 ms |
5016 KB |
Output is correct |
15 |
Correct |
3 ms |
4940 KB |
Output is correct |
16 |
Correct |
3 ms |
4940 KB |
Output is correct |
17 |
Correct |
3 ms |
4940 KB |
Output is correct |
18 |
Correct |
4 ms |
4940 KB |
Output is correct |
19 |
Correct |
3 ms |
4940 KB |
Output is correct |
20 |
Correct |
3 ms |
4940 KB |
Output is correct |
21 |
Correct |
4 ms |
5196 KB |
Output is correct |
22 |
Correct |
4 ms |
5020 KB |
Output is correct |
23 |
Correct |
4 ms |
4940 KB |
Output is correct |
24 |
Correct |
4 ms |
4940 KB |
Output is correct |
25 |
Correct |
3 ms |
4940 KB |
Output is correct |
26 |
Correct |
4 ms |
4940 KB |
Output is correct |
27 |
Correct |
4 ms |
4940 KB |
Output is correct |
28 |
Correct |
4 ms |
4940 KB |
Output is correct |
29 |
Correct |
4 ms |
4940 KB |
Output is correct |
30 |
Correct |
3 ms |
4940 KB |
Output is correct |
31 |
Correct |
3 ms |
4940 KB |
Output is correct |
32 |
Correct |
3 ms |
4940 KB |
Output is correct |
33 |
Correct |
3 ms |
4940 KB |
Output is correct |
34 |
Correct |
4 ms |
4940 KB |
Output is correct |
35 |
Correct |
4 ms |
4940 KB |
Output is correct |
36 |
Correct |
4 ms |
5012 KB |
Output is correct |
37 |
Correct |
4 ms |
5012 KB |
Output is correct |
38 |
Correct |
4 ms |
5024 KB |
Output is correct |
39 |
Correct |
4 ms |
5068 KB |
Output is correct |
40 |
Correct |
4 ms |
5196 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
3 ms |
4940 KB |
Output is correct |
2 |
Correct |
4 ms |
4940 KB |
Output is correct |
3 |
Correct |
3 ms |
4940 KB |
Output is correct |
4 |
Correct |
4 ms |
4940 KB |
Output is correct |
5 |
Correct |
4 ms |
4940 KB |
Output is correct |
6 |
Correct |
3 ms |
4940 KB |
Output is correct |
7 |
Correct |
3 ms |
4940 KB |
Output is correct |
8 |
Correct |
3 ms |
4940 KB |
Output is correct |
9 |
Correct |
3 ms |
4940 KB |
Output is correct |
10 |
Correct |
3 ms |
4940 KB |
Output is correct |
11 |
Correct |
3 ms |
4940 KB |
Output is correct |
12 |
Correct |
3 ms |
4940 KB |
Output is correct |
13 |
Correct |
3 ms |
5012 KB |
Output is correct |
14 |
Correct |
3 ms |
5016 KB |
Output is correct |
15 |
Correct |
3 ms |
4940 KB |
Output is correct |
16 |
Correct |
3 ms |
4940 KB |
Output is correct |
17 |
Correct |
3 ms |
4940 KB |
Output is correct |
18 |
Correct |
4 ms |
4940 KB |
Output is correct |
19 |
Correct |
3 ms |
4940 KB |
Output is correct |
20 |
Correct |
3 ms |
4940 KB |
Output is correct |
21 |
Correct |
4 ms |
5196 KB |
Output is correct |
22 |
Correct |
4 ms |
5020 KB |
Output is correct |
23 |
Correct |
4 ms |
4940 KB |
Output is correct |
24 |
Correct |
4 ms |
4940 KB |
Output is correct |
25 |
Correct |
3 ms |
4940 KB |
Output is correct |
26 |
Correct |
4 ms |
4940 KB |
Output is correct |
27 |
Correct |
4 ms |
4940 KB |
Output is correct |
28 |
Correct |
4 ms |
4940 KB |
Output is correct |
29 |
Correct |
4 ms |
4940 KB |
Output is correct |
30 |
Correct |
3 ms |
4940 KB |
Output is correct |
31 |
Correct |
3 ms |
4940 KB |
Output is correct |
32 |
Correct |
3 ms |
4940 KB |
Output is correct |
33 |
Correct |
3 ms |
4940 KB |
Output is correct |
34 |
Correct |
4 ms |
4940 KB |
Output is correct |
35 |
Correct |
4 ms |
4940 KB |
Output is correct |
36 |
Correct |
4 ms |
5012 KB |
Output is correct |
37 |
Correct |
4 ms |
5012 KB |
Output is correct |
38 |
Correct |
4 ms |
5024 KB |
Output is correct |
39 |
Correct |
4 ms |
5068 KB |
Output is correct |
40 |
Correct |
4 ms |
5196 KB |
Output is correct |
41 |
Correct |
50 ms |
9352 KB |
Output is correct |
42 |
Correct |
50 ms |
6708 KB |
Output is correct |
43 |
Correct |
37 ms |
6732 KB |
Output is correct |
44 |
Correct |
37 ms |
6680 KB |
Output is correct |
45 |
Correct |
34 ms |
6720 KB |
Output is correct |
46 |
Correct |
92 ms |
8372 KB |
Output is correct |
47 |
Correct |
91 ms |
8376 KB |
Output is correct |
48 |
Correct |
90 ms |
8296 KB |
Output is correct |
49 |
Correct |
79 ms |
8344 KB |
Output is correct |
50 |
Correct |
23 ms |
5748 KB |
Output is correct |
51 |
Correct |
23 ms |
5744 KB |
Output is correct |
52 |
Correct |
21 ms |
5708 KB |
Output is correct |
53 |
Correct |
41 ms |
6220 KB |
Output is correct |
54 |
Correct |
39 ms |
6388 KB |
Output is correct |
55 |
Correct |
42 ms |
6244 KB |
Output is correct |
56 |
Correct |
5 ms |
5208 KB |
Output is correct |
57 |
Correct |
11 ms |
8860 KB |
Output is correct |
58 |
Correct |
39 ms |
21956 KB |
Output is correct |
59 |
Correct |
100 ms |
23952 KB |
Output is correct |
60 |
Correct |
55 ms |
9716 KB |
Output is correct |
61 |
Correct |
72 ms |
9224 KB |
Output is correct |