#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 current_dep;
int pre[mxn][19];
void dfs2(int u, int p){
for(auto e : g[u]){
if(e == p || deleted[e]) continue;
pre[e][current_dep] = pre[u][current_dep] + 1;
dfs2(e, u);
}
}
int link[mxn];
int cdep[mxn];
void decompose(int u, int p, int d){
dfs0(u, u);
cn = sub[u];
int cen = dfs1(u, u);
link[cen] = p;
current_dep = d;
cdep[cen] = d;
pre[cen][d] = 0;
dfs2(cen, cen);
deleted[cen] = true;
for(auto e : g[cen]){
if(!deleted[e]){
decompose(e, cen, d + 1);
}
}
}
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){
//optimization :
int w = minw[x] + pre[u][cdep[x]];
//slow version :
//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){
//optimization :
int w = pre[u][cdep[x]];
//slow version :
//int w = dep[x] + dep[u] - 2*dep[lca(x, u)];
minw[x] = min(minw[x], w);
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, 0);
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 |
4992 KB |
Output is correct |
2 |
Correct |
5 ms |
4940 KB |
Output is correct |
3 |
Correct |
4 ms |
5068 KB |
Output is correct |
4 |
Correct |
4 ms |
5024 KB |
Output is correct |
5 |
Correct |
4 ms |
4940 KB |
Output is correct |
6 |
Correct |
5 ms |
5068 KB |
Output is correct |
7 |
Correct |
5 ms |
5068 KB |
Output is correct |
8 |
Correct |
5 ms |
5024 KB |
Output is correct |
9 |
Correct |
5 ms |
5068 KB |
Output is correct |
10 |
Correct |
5 ms |
5068 KB |
Output is correct |
11 |
Correct |
4 ms |
5068 KB |
Output is correct |
12 |
Correct |
4 ms |
5020 KB |
Output is correct |
13 |
Correct |
4 ms |
5068 KB |
Output is correct |
14 |
Correct |
4 ms |
5016 KB |
Output is correct |
15 |
Correct |
4 ms |
5068 KB |
Output is correct |
16 |
Correct |
4 ms |
5068 KB |
Output is correct |
17 |
Correct |
4 ms |
5068 KB |
Output is correct |
18 |
Correct |
4 ms |
5068 KB |
Output is correct |
19 |
Correct |
4 ms |
5020 KB |
Output is correct |
20 |
Correct |
5 ms |
5068 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
4 ms |
4992 KB |
Output is correct |
2 |
Correct |
5 ms |
4940 KB |
Output is correct |
3 |
Correct |
4 ms |
5068 KB |
Output is correct |
4 |
Correct |
4 ms |
5024 KB |
Output is correct |
5 |
Correct |
4 ms |
4940 KB |
Output is correct |
6 |
Correct |
5 ms |
5068 KB |
Output is correct |
7 |
Correct |
5 ms |
5068 KB |
Output is correct |
8 |
Correct |
5 ms |
5024 KB |
Output is correct |
9 |
Correct |
5 ms |
5068 KB |
Output is correct |
10 |
Correct |
5 ms |
5068 KB |
Output is correct |
11 |
Correct |
4 ms |
5068 KB |
Output is correct |
12 |
Correct |
4 ms |
5020 KB |
Output is correct |
13 |
Correct |
4 ms |
5068 KB |
Output is correct |
14 |
Correct |
4 ms |
5016 KB |
Output is correct |
15 |
Correct |
4 ms |
5068 KB |
Output is correct |
16 |
Correct |
4 ms |
5068 KB |
Output is correct |
17 |
Correct |
4 ms |
5068 KB |
Output is correct |
18 |
Correct |
4 ms |
5068 KB |
Output is correct |
19 |
Correct |
4 ms |
5020 KB |
Output is correct |
20 |
Correct |
5 ms |
5068 KB |
Output is correct |
21 |
Correct |
6 ms |
5452 KB |
Output is correct |
22 |
Correct |
5 ms |
5068 KB |
Output is correct |
23 |
Correct |
5 ms |
5068 KB |
Output is correct |
24 |
Correct |
4 ms |
5068 KB |
Output is correct |
25 |
Correct |
6 ms |
5196 KB |
Output is correct |
26 |
Correct |
5 ms |
5280 KB |
Output is correct |
27 |
Correct |
5 ms |
5276 KB |
Output is correct |
28 |
Correct |
6 ms |
5324 KB |
Output is correct |
29 |
Correct |
5 ms |
5324 KB |
Output is correct |
30 |
Correct |
5 ms |
5324 KB |
Output is correct |
31 |
Correct |
5 ms |
5280 KB |
Output is correct |
32 |
Correct |
5 ms |
5284 KB |
Output is correct |
33 |
Correct |
5 ms |
5324 KB |
Output is correct |
34 |
Correct |
5 ms |
5288 KB |
Output is correct |
35 |
Correct |
5 ms |
5272 KB |
Output is correct |
36 |
Correct |
6 ms |
5292 KB |
Output is correct |
37 |
Correct |
5 ms |
5412 KB |
Output is correct |
38 |
Correct |
6 ms |
5408 KB |
Output is correct |
39 |
Correct |
6 ms |
5412 KB |
Output is correct |
40 |
Correct |
6 ms |
5452 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
4 ms |
4992 KB |
Output is correct |
2 |
Correct |
5 ms |
4940 KB |
Output is correct |
3 |
Correct |
4 ms |
5068 KB |
Output is correct |
4 |
Correct |
4 ms |
5024 KB |
Output is correct |
5 |
Correct |
4 ms |
4940 KB |
Output is correct |
6 |
Correct |
5 ms |
5068 KB |
Output is correct |
7 |
Correct |
5 ms |
5068 KB |
Output is correct |
8 |
Correct |
5 ms |
5024 KB |
Output is correct |
9 |
Correct |
5 ms |
5068 KB |
Output is correct |
10 |
Correct |
5 ms |
5068 KB |
Output is correct |
11 |
Correct |
4 ms |
5068 KB |
Output is correct |
12 |
Correct |
4 ms |
5020 KB |
Output is correct |
13 |
Correct |
4 ms |
5068 KB |
Output is correct |
14 |
Correct |
4 ms |
5016 KB |
Output is correct |
15 |
Correct |
4 ms |
5068 KB |
Output is correct |
16 |
Correct |
4 ms |
5068 KB |
Output is correct |
17 |
Correct |
4 ms |
5068 KB |
Output is correct |
18 |
Correct |
4 ms |
5068 KB |
Output is correct |
19 |
Correct |
4 ms |
5020 KB |
Output is correct |
20 |
Correct |
5 ms |
5068 KB |
Output is correct |
21 |
Correct |
6 ms |
5452 KB |
Output is correct |
22 |
Correct |
5 ms |
5068 KB |
Output is correct |
23 |
Correct |
5 ms |
5068 KB |
Output is correct |
24 |
Correct |
4 ms |
5068 KB |
Output is correct |
25 |
Correct |
6 ms |
5196 KB |
Output is correct |
26 |
Correct |
5 ms |
5280 KB |
Output is correct |
27 |
Correct |
5 ms |
5276 KB |
Output is correct |
28 |
Correct |
6 ms |
5324 KB |
Output is correct |
29 |
Correct |
5 ms |
5324 KB |
Output is correct |
30 |
Correct |
5 ms |
5324 KB |
Output is correct |
31 |
Correct |
5 ms |
5280 KB |
Output is correct |
32 |
Correct |
5 ms |
5284 KB |
Output is correct |
33 |
Correct |
5 ms |
5324 KB |
Output is correct |
34 |
Correct |
5 ms |
5288 KB |
Output is correct |
35 |
Correct |
5 ms |
5272 KB |
Output is correct |
36 |
Correct |
6 ms |
5292 KB |
Output is correct |
37 |
Correct |
5 ms |
5412 KB |
Output is correct |
38 |
Correct |
6 ms |
5408 KB |
Output is correct |
39 |
Correct |
6 ms |
5412 KB |
Output is correct |
40 |
Correct |
6 ms |
5452 KB |
Output is correct |
41 |
Correct |
151 ms |
44532 KB |
Output is correct |
42 |
Correct |
222 ms |
25984 KB |
Output is correct |
43 |
Correct |
176 ms |
25892 KB |
Output is correct |
44 |
Correct |
163 ms |
25828 KB |
Output is correct |
45 |
Correct |
210 ms |
25916 KB |
Output is correct |
46 |
Correct |
529 ms |
46472 KB |
Output is correct |
47 |
Correct |
582 ms |
46380 KB |
Output is correct |
48 |
Correct |
502 ms |
46528 KB |
Output is correct |
49 |
Correct |
431 ms |
46400 KB |
Output is correct |
50 |
Correct |
107 ms |
26268 KB |
Output is correct |
51 |
Correct |
114 ms |
26304 KB |
Output is correct |
52 |
Correct |
157 ms |
26320 KB |
Output is correct |
53 |
Correct |
277 ms |
47184 KB |
Output is correct |
54 |
Correct |
301 ms |
47416 KB |
Output is correct |
55 |
Correct |
355 ms |
47264 KB |
Output is correct |
56 |
Correct |
6 ms |
5544 KB |
Output is correct |
57 |
Correct |
28 ms |
11072 KB |
Output is correct |
58 |
Correct |
120 ms |
32828 KB |
Output is correct |
59 |
Correct |
423 ms |
54152 KB |
Output is correct |
60 |
Correct |
162 ms |
45496 KB |
Output is correct |
61 |
Correct |
213 ms |
44256 KB |
Output is correct |