#include <bits/stdc++.h>
#define ll long long
#define f first
#define s second
#define pii pair<int,int>
#define pll pair<ll,ll>
#define pb push_back
#define epb emplace_back
using namespace std;
const int nmax = 2e5 + 1;
vector <vector <pii> > cent(nmax);
vector <bool> marked(nmax);
vector <int> sz(nmax);
vector <int> mx(nmax);
vector <vector <int> > g(nmax);
vector <int> cur(nmax, 1e9);
void dfs(int v, int e = -1){
sz[v] = 1;
mx[v] = 0;
for(int to : g[v]){
if(marked[to]) continue;
if(to == e) continue;
dfs(to, v);
sz[v] += sz[to];
mx[v] = max(mx[v], sz[to]);
}
}
int find_cen(int v, int s, int e = -1){
if(mx[v] <= s / 2){
if(sz[v] >= s / 2) return v;
}
for(int to : g[v]){
if(to == e || marked[to]) continue;
int x = find_cen(to, s, v);
if(x != -1) return x;
}
return -1;
}
void DFS(int v, int d, int st, int e = -1){
cent[v].pb({d, st});
for(int to : g[v]){
if(to == e || marked[to]) continue;
DFS(to, d + 1, st, v);
}
}
void rec(int v){
dfs(v);
int x = find_cen(v, sz[v]);
DFS(x, 0, x);
marked[x] = true;
for(int to : g[x]){
if(!marked[to])
rec(to);
}
}
int getmn(int v){
int ans = 1e9;
for(auto cc : cent[v]){
int x = cc.s, y = cc.f;
ans = min(ans, cur[x] + y);
}
return ans;
}
void mark(int v){
for(auto cc : cent[v]){
int x = cc.s, y = cc.f;
cur[x] = min(cur[x], y);
}
}
vector <pii> vv;
void stupidguy(int v, int d, int e = -1){
vv.pb({d, v});
for(int to : g[v]){
if(to == e) continue;
stupidguy(to, d + 1, v);
}
}
int main(){
ios_base::sync_with_stdio(false); cin.tie(0);
int n; cin >> n;
int D; cin >> D;
for(int i = 1; i < n; i++){
int x; cin >> x;
g[x].pb(i);
g[i].pb(x);
}
rec(1);
int ans = 0;
stupidguy(1, 0);
sort(vv.begin(), vv.end());
for(int i = vv.size() - 1; i >= 0; i--){
int x = vv[i].s;
if(getmn(x) >= D){
ans++;
mark(x);
}
}
cout << ans;
return 0;
}
/* - - - - - - - - - - - - - -
| ## |
| # ## # |
| ##### ## ##### |
| # ## # |
| ## |
| ##########################|
| ## |
| # ## # |
| ##### ## ##### |
| # ## # |
| ## |
- - - - - - - - - - - - - -
*/
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
6 ms |
11988 KB |
Output is correct |
2 |
Correct |
8 ms |
12072 KB |
Output is correct |
3 |
Correct |
6 ms |
11988 KB |
Output is correct |
4 |
Correct |
7 ms |
11988 KB |
Output is correct |
5 |
Correct |
8 ms |
11988 KB |
Output is correct |
6 |
Correct |
6 ms |
11988 KB |
Output is correct |
7 |
Correct |
7 ms |
11988 KB |
Output is correct |
8 |
Correct |
6 ms |
11988 KB |
Output is correct |
9 |
Correct |
7 ms |
11988 KB |
Output is correct |
10 |
Correct |
7 ms |
11988 KB |
Output is correct |
11 |
Correct |
9 ms |
12116 KB |
Output is correct |
12 |
Correct |
7 ms |
11988 KB |
Output is correct |
13 |
Correct |
9 ms |
11988 KB |
Output is correct |
14 |
Correct |
6 ms |
11988 KB |
Output is correct |
15 |
Correct |
9 ms |
12100 KB |
Output is correct |
16 |
Correct |
6 ms |
11988 KB |
Output is correct |
17 |
Correct |
7 ms |
11988 KB |
Output is correct |
18 |
Correct |
6 ms |
11988 KB |
Output is correct |
19 |
Correct |
7 ms |
11988 KB |
Output is correct |
20 |
Correct |
6 ms |
12112 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
6 ms |
11988 KB |
Output is correct |
2 |
Correct |
8 ms |
12072 KB |
Output is correct |
3 |
Correct |
6 ms |
11988 KB |
Output is correct |
4 |
Correct |
7 ms |
11988 KB |
Output is correct |
5 |
Correct |
8 ms |
11988 KB |
Output is correct |
6 |
Correct |
6 ms |
11988 KB |
Output is correct |
7 |
Correct |
7 ms |
11988 KB |
Output is correct |
8 |
Correct |
6 ms |
11988 KB |
Output is correct |
9 |
Correct |
7 ms |
11988 KB |
Output is correct |
10 |
Correct |
7 ms |
11988 KB |
Output is correct |
11 |
Correct |
9 ms |
12116 KB |
Output is correct |
12 |
Correct |
7 ms |
11988 KB |
Output is correct |
13 |
Correct |
9 ms |
11988 KB |
Output is correct |
14 |
Correct |
6 ms |
11988 KB |
Output is correct |
15 |
Correct |
9 ms |
12100 KB |
Output is correct |
16 |
Correct |
6 ms |
11988 KB |
Output is correct |
17 |
Correct |
7 ms |
11988 KB |
Output is correct |
18 |
Correct |
6 ms |
11988 KB |
Output is correct |
19 |
Correct |
7 ms |
11988 KB |
Output is correct |
20 |
Correct |
6 ms |
12112 KB |
Output is correct |
21 |
Correct |
7 ms |
12500 KB |
Output is correct |
22 |
Correct |
10 ms |
12104 KB |
Output is correct |
23 |
Correct |
7 ms |
12160 KB |
Output is correct |
24 |
Correct |
6 ms |
12104 KB |
Output is correct |
25 |
Correct |
7 ms |
12244 KB |
Output is correct |
26 |
Correct |
7 ms |
12244 KB |
Output is correct |
27 |
Correct |
7 ms |
12232 KB |
Output is correct |
28 |
Correct |
8 ms |
12236 KB |
Output is correct |
29 |
Correct |
7 ms |
12244 KB |
Output is correct |
30 |
Correct |
9 ms |
12300 KB |
Output is correct |
31 |
Correct |
8 ms |
12244 KB |
Output is correct |
32 |
Correct |
7 ms |
12244 KB |
Output is correct |
33 |
Correct |
9 ms |
12224 KB |
Output is correct |
34 |
Correct |
7 ms |
12236 KB |
Output is correct |
35 |
Correct |
7 ms |
12236 KB |
Output is correct |
36 |
Correct |
7 ms |
12272 KB |
Output is correct |
37 |
Correct |
7 ms |
12244 KB |
Output is correct |
38 |
Correct |
8 ms |
12372 KB |
Output is correct |
39 |
Correct |
7 ms |
12324 KB |
Output is correct |
40 |
Correct |
7 ms |
12500 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
6 ms |
11988 KB |
Output is correct |
2 |
Correct |
8 ms |
12072 KB |
Output is correct |
3 |
Correct |
6 ms |
11988 KB |
Output is correct |
4 |
Correct |
7 ms |
11988 KB |
Output is correct |
5 |
Correct |
8 ms |
11988 KB |
Output is correct |
6 |
Correct |
6 ms |
11988 KB |
Output is correct |
7 |
Correct |
7 ms |
11988 KB |
Output is correct |
8 |
Correct |
6 ms |
11988 KB |
Output is correct |
9 |
Correct |
7 ms |
11988 KB |
Output is correct |
10 |
Correct |
7 ms |
11988 KB |
Output is correct |
11 |
Correct |
9 ms |
12116 KB |
Output is correct |
12 |
Correct |
7 ms |
11988 KB |
Output is correct |
13 |
Correct |
9 ms |
11988 KB |
Output is correct |
14 |
Correct |
6 ms |
11988 KB |
Output is correct |
15 |
Correct |
9 ms |
12100 KB |
Output is correct |
16 |
Correct |
6 ms |
11988 KB |
Output is correct |
17 |
Correct |
7 ms |
11988 KB |
Output is correct |
18 |
Correct |
6 ms |
11988 KB |
Output is correct |
19 |
Correct |
7 ms |
11988 KB |
Output is correct |
20 |
Correct |
6 ms |
12112 KB |
Output is correct |
21 |
Correct |
7 ms |
12500 KB |
Output is correct |
22 |
Correct |
10 ms |
12104 KB |
Output is correct |
23 |
Correct |
7 ms |
12160 KB |
Output is correct |
24 |
Correct |
6 ms |
12104 KB |
Output is correct |
25 |
Correct |
7 ms |
12244 KB |
Output is correct |
26 |
Correct |
7 ms |
12244 KB |
Output is correct |
27 |
Correct |
7 ms |
12232 KB |
Output is correct |
28 |
Correct |
8 ms |
12236 KB |
Output is correct |
29 |
Correct |
7 ms |
12244 KB |
Output is correct |
30 |
Correct |
9 ms |
12300 KB |
Output is correct |
31 |
Correct |
8 ms |
12244 KB |
Output is correct |
32 |
Correct |
7 ms |
12244 KB |
Output is correct |
33 |
Correct |
9 ms |
12224 KB |
Output is correct |
34 |
Correct |
7 ms |
12236 KB |
Output is correct |
35 |
Correct |
7 ms |
12236 KB |
Output is correct |
36 |
Correct |
7 ms |
12272 KB |
Output is correct |
37 |
Correct |
7 ms |
12244 KB |
Output is correct |
38 |
Correct |
8 ms |
12372 KB |
Output is correct |
39 |
Correct |
7 ms |
12324 KB |
Output is correct |
40 |
Correct |
7 ms |
12500 KB |
Output is correct |
41 |
Correct |
121 ms |
30156 KB |
Output is correct |
42 |
Correct |
206 ms |
29012 KB |
Output is correct |
43 |
Correct |
198 ms |
29404 KB |
Output is correct |
44 |
Correct |
202 ms |
29232 KB |
Output is correct |
45 |
Correct |
187 ms |
28980 KB |
Output is correct |
46 |
Correct |
529 ms |
46028 KB |
Output is correct |
47 |
Correct |
527 ms |
46840 KB |
Output is correct |
48 |
Correct |
590 ms |
47036 KB |
Output is correct |
49 |
Correct |
538 ms |
47180 KB |
Output is correct |
50 |
Correct |
117 ms |
25204 KB |
Output is correct |
51 |
Correct |
122 ms |
25588 KB |
Output is correct |
52 |
Correct |
134 ms |
25536 KB |
Output is correct |
53 |
Correct |
435 ms |
39864 KB |
Output is correct |
54 |
Correct |
304 ms |
39148 KB |
Output is correct |
55 |
Correct |
364 ms |
39328 KB |
Output is correct |
56 |
Correct |
12 ms |
12628 KB |
Output is correct |
57 |
Correct |
28 ms |
17492 KB |
Output is correct |
58 |
Correct |
134 ms |
40156 KB |
Output is correct |
59 |
Correct |
472 ms |
67352 KB |
Output is correct |
60 |
Correct |
125 ms |
30680 KB |
Output is correct |
61 |
Correct |
230 ms |
37276 KB |
Output is correct |