#include <bits/stdc++.h>
#define fr(i, n, m) for(int i = (n); i < (m); i ++)
#define pb push_back
#define st first
#define nd second
#define pq priority_queue
#define all(x) begin(x), end(x)
using namespace std;
typedef long long ll;
typedef long double ld;
typedef pair<ll,ll> pii;
const ll inf = 1e18;
const int i_inf = 1e9;
const ll mod = 1e9+7;
mt19937 _rand(time(NULL));
const int mxn = 2e5;
int n, d;
vector<int> g[mxn];
int sub[mxn];
bool deleted[mxn];
int cn;
int dep[mxn];
int sparse[mxn][19];
void dfs(int u, int p){
sparse[u][0] = p;
fr(i, 1, 19) sparse[u][i] = sparse[sparse[u][i-1]][i-1];
for(auto e : g[u]){
if(e == p) continue;
dep[e] = dep[u] + 1;
dfs(e, u);
}
}
void dfs0(int u, int p){
sub[u] = 1;
for(auto e : g[u]){
if(e == p || deleted[e]) continue;
dfs0(e, u);
sub[u] += sub[e];
}
}
int dfs1(int u, int p){
for(auto e : g[u]){
if(e == p || deleted[e]) continue;
if(sub[e] > cn /2) return dfs1(e, u);
}
return u;
}
int link[mxn];
void decompose(int u, int p){
dfs0(u, u);
cn = sub[u];
int cen = dfs1(u, u);
link[cen] = p;
deleted[cen] = true;
for(auto e : g[cen]){
if(!deleted[e]){
decompose(e, cen);
}
}
}
int lca(int a, int b){
int d = min(dep[a], dep[b]);
for(int i = 18; i >= 0; i --){
if(dep[a] - (1<<i) >= d){
a = sparse[a][i];
}
if(dep[b] - (1<<i) >= d){
b = sparse[b][i];
}
}
if(a == b) return a;
for(int i = 18; i >= 0; i--){
if(sparse[a][i] != sparse[b][i]){
a = sparse[a][i];
b = sparse[b][i];
}
}
return sparse[a][0];
}
int minw[mxn];
bool check(int u){
int x = u;
while(x != -1){
int w = minw[x] + dep[x] + dep[u] - 2*dep[lca(x, u)];
if(w < d) return false;
x = link[x];
}
return true;
}
void update(int u){
int x = u;
while(x != -1){
minw[x] = min(minw[x], dep[x] + dep[u] - 2*dep[lca(x, u)]);
x = link[x];
}
}
void solve(){
cin >> n >> d;
fr(i, 1, n){
int x;
cin >> x;
g[i].pb(x);
g[x].pb(i);
}
dfs(0, 0);
decompose(0, -1);
vector<int> v;
fr(i, 0, n) v.pb(i);
sort(all(v), [](const int &i, const int &j){
return dep[i] > dep[j];
});
fr(i, 0, n){
minw[i] = 1e9;
}
int ans = 0;
for(auto u : v){
if(check(u)){
update(u);
++ans;
}
}
cout<<ans<<endl;
}
int main(){
ios_base::sync_with_stdio(false);
cin.tie(NULL);
cout.tie(NULL);
solve();
}
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
4 ms |
4968 KB |
Output is correct |
2 |
Correct |
5 ms |
4940 KB |
Output is correct |
3 |
Correct |
4 ms |
4940 KB |
Output is correct |
4 |
Correct |
4 ms |
4984 KB |
Output is correct |
5 |
Correct |
4 ms |
4940 KB |
Output is correct |
6 |
Correct |
4 ms |
4940 KB |
Output is correct |
7 |
Correct |
4 ms |
4976 KB |
Output is correct |
8 |
Correct |
4 ms |
4940 KB |
Output is correct |
9 |
Correct |
5 ms |
5028 KB |
Output is correct |
10 |
Correct |
4 ms |
5024 KB |
Output is correct |
11 |
Correct |
4 ms |
4940 KB |
Output is correct |
12 |
Correct |
5 ms |
4940 KB |
Output is correct |
13 |
Correct |
5 ms |
4960 KB |
Output is correct |
14 |
Correct |
4 ms |
5024 KB |
Output is correct |
15 |
Correct |
4 ms |
4940 KB |
Output is correct |
16 |
Correct |
4 ms |
4940 KB |
Output is correct |
17 |
Correct |
3 ms |
4940 KB |
Output is correct |
18 |
Correct |
5 ms |
5028 KB |
Output is correct |
19 |
Correct |
5 ms |
4940 KB |
Output is correct |
20 |
Correct |
6 ms |
4940 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
4 ms |
4968 KB |
Output is correct |
2 |
Correct |
5 ms |
4940 KB |
Output is correct |
3 |
Correct |
4 ms |
4940 KB |
Output is correct |
4 |
Correct |
4 ms |
4984 KB |
Output is correct |
5 |
Correct |
4 ms |
4940 KB |
Output is correct |
6 |
Correct |
4 ms |
4940 KB |
Output is correct |
7 |
Correct |
4 ms |
4976 KB |
Output is correct |
8 |
Correct |
4 ms |
4940 KB |
Output is correct |
9 |
Correct |
5 ms |
5028 KB |
Output is correct |
10 |
Correct |
4 ms |
5024 KB |
Output is correct |
11 |
Correct |
4 ms |
4940 KB |
Output is correct |
12 |
Correct |
5 ms |
4940 KB |
Output is correct |
13 |
Correct |
5 ms |
4960 KB |
Output is correct |
14 |
Correct |
4 ms |
5024 KB |
Output is correct |
15 |
Correct |
4 ms |
4940 KB |
Output is correct |
16 |
Correct |
4 ms |
4940 KB |
Output is correct |
17 |
Correct |
3 ms |
4940 KB |
Output is correct |
18 |
Correct |
5 ms |
5028 KB |
Output is correct |
19 |
Correct |
5 ms |
4940 KB |
Output is correct |
20 |
Correct |
6 ms |
4940 KB |
Output is correct |
21 |
Correct |
6 ms |
5324 KB |
Output is correct |
22 |
Correct |
5 ms |
5068 KB |
Output is correct |
23 |
Correct |
5 ms |
5024 KB |
Output is correct |
24 |
Correct |
5 ms |
5128 KB |
Output is correct |
25 |
Correct |
7 ms |
5152 KB |
Output is correct |
26 |
Correct |
5 ms |
5068 KB |
Output is correct |
27 |
Correct |
6 ms |
5152 KB |
Output is correct |
28 |
Correct |
6 ms |
5196 KB |
Output is correct |
29 |
Correct |
7 ms |
5196 KB |
Output is correct |
30 |
Correct |
5 ms |
5196 KB |
Output is correct |
31 |
Correct |
6 ms |
5196 KB |
Output is correct |
32 |
Correct |
5 ms |
5196 KB |
Output is correct |
33 |
Correct |
6 ms |
5196 KB |
Output is correct |
34 |
Correct |
4 ms |
5196 KB |
Output is correct |
35 |
Correct |
6 ms |
5196 KB |
Output is correct |
36 |
Correct |
5 ms |
5152 KB |
Output is correct |
37 |
Correct |
5 ms |
5196 KB |
Output is correct |
38 |
Correct |
5 ms |
5196 KB |
Output is correct |
39 |
Correct |
5 ms |
5196 KB |
Output is correct |
40 |
Correct |
7 ms |
5324 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
4 ms |
4968 KB |
Output is correct |
2 |
Correct |
5 ms |
4940 KB |
Output is correct |
3 |
Correct |
4 ms |
4940 KB |
Output is correct |
4 |
Correct |
4 ms |
4984 KB |
Output is correct |
5 |
Correct |
4 ms |
4940 KB |
Output is correct |
6 |
Correct |
4 ms |
4940 KB |
Output is correct |
7 |
Correct |
4 ms |
4976 KB |
Output is correct |
8 |
Correct |
4 ms |
4940 KB |
Output is correct |
9 |
Correct |
5 ms |
5028 KB |
Output is correct |
10 |
Correct |
4 ms |
5024 KB |
Output is correct |
11 |
Correct |
4 ms |
4940 KB |
Output is correct |
12 |
Correct |
5 ms |
4940 KB |
Output is correct |
13 |
Correct |
5 ms |
4960 KB |
Output is correct |
14 |
Correct |
4 ms |
5024 KB |
Output is correct |
15 |
Correct |
4 ms |
4940 KB |
Output is correct |
16 |
Correct |
4 ms |
4940 KB |
Output is correct |
17 |
Correct |
3 ms |
4940 KB |
Output is correct |
18 |
Correct |
5 ms |
5028 KB |
Output is correct |
19 |
Correct |
5 ms |
4940 KB |
Output is correct |
20 |
Correct |
6 ms |
4940 KB |
Output is correct |
21 |
Correct |
6 ms |
5324 KB |
Output is correct |
22 |
Correct |
5 ms |
5068 KB |
Output is correct |
23 |
Correct |
5 ms |
5024 KB |
Output is correct |
24 |
Correct |
5 ms |
5128 KB |
Output is correct |
25 |
Correct |
7 ms |
5152 KB |
Output is correct |
26 |
Correct |
5 ms |
5068 KB |
Output is correct |
27 |
Correct |
6 ms |
5152 KB |
Output is correct |
28 |
Correct |
6 ms |
5196 KB |
Output is correct |
29 |
Correct |
7 ms |
5196 KB |
Output is correct |
30 |
Correct |
5 ms |
5196 KB |
Output is correct |
31 |
Correct |
6 ms |
5196 KB |
Output is correct |
32 |
Correct |
5 ms |
5196 KB |
Output is correct |
33 |
Correct |
6 ms |
5196 KB |
Output is correct |
34 |
Correct |
4 ms |
5196 KB |
Output is correct |
35 |
Correct |
6 ms |
5196 KB |
Output is correct |
36 |
Correct |
5 ms |
5152 KB |
Output is correct |
37 |
Correct |
5 ms |
5196 KB |
Output is correct |
38 |
Correct |
5 ms |
5196 KB |
Output is correct |
39 |
Correct |
5 ms |
5196 KB |
Output is correct |
40 |
Correct |
7 ms |
5324 KB |
Output is correct |
41 |
Correct |
145 ms |
30332 KB |
Output is correct |
42 |
Correct |
242 ms |
18468 KB |
Output is correct |
43 |
Correct |
183 ms |
18404 KB |
Output is correct |
44 |
Correct |
233 ms |
18364 KB |
Output is correct |
45 |
Correct |
174 ms |
18428 KB |
Output is correct |
46 |
Correct |
520 ms |
31648 KB |
Output is correct |
47 |
Correct |
494 ms |
31752 KB |
Output is correct |
48 |
Correct |
439 ms |
31764 KB |
Output is correct |
49 |
Correct |
619 ms |
31676 KB |
Output is correct |
50 |
Correct |
120 ms |
18684 KB |
Output is correct |
51 |
Correct |
121 ms |
18604 KB |
Output is correct |
52 |
Correct |
111 ms |
18696 KB |
Output is correct |
53 |
Correct |
274 ms |
32204 KB |
Output is correct |
54 |
Correct |
312 ms |
32164 KB |
Output is correct |
55 |
Correct |
282 ms |
32244 KB |
Output is correct |
56 |
Correct |
8 ms |
5452 KB |
Output is correct |
57 |
Correct |
37 ms |
9412 KB |
Output is correct |
58 |
Correct |
192 ms |
25504 KB |
Output is correct |
59 |
Correct |
514 ms |
39492 KB |
Output is correct |
60 |
Correct |
167 ms |
31032 KB |
Output is correct |
61 |
Correct |
286 ms |
30256 KB |
Output is correct |