#include <bits/stdc++.h>
#define ll long long
const int nmax = 2e5 + 5;
const int mod = 1e9 + 7;
const int lg = 19;
const int M = 1 << 18;
const ll oo = 1e9 + 1;
#define fi first
#define se second
#define pii pair<int, ll>
using namespace std;
int n, d, m = 0;
int h[nmax], idx[nmax], par[nmax], sz[nmax];
int up[nmax][lg + 1], st[nmax * 2], tour[nmax * 2], rmq[nmax * 2][lg + 1];
bool vis[nmax];
vector<int> adj[nmax];
void dfs(int u, int p){
tour[++m] = u;
for(auto v : adj[u]){
if(v == p) continue;
h[v] = h[u] + 1;
up[v][0] = u;
for(int j = 1; j <= lg; ++j) up[v][j] = up[up[v][j - 1]][j - 1];
dfs(v, u);
tour[++m] = u;
}
}
void dfs1(int u, int p){
sz[u] = 1;
for(auto v : adj[u]){
if(vis[v] || v == p) continue;
dfs1(v, u);
sz[u] += sz[v];
}
}
int get(int l, int r){
if(l > r) swap(l, r);
int k = __lg(r - l + 1);
return min(rmq[l][k], rmq[r - (1 << k) + 1][k]);
}
int dist(int u, int v){
return h[u] + h[v] - 2 * get(st[u], st[v]);
}
int cntw, root;
void dfs2(int u, int p){
for(auto v : adj[u]){
if(vis[v] || v == p) continue;
if(sz[v] > cntw / 2) return dfs2(v, u);
}
root = u;
}
int build(int u){
dfs1(u, -1); cntw = sz[u];
dfs2(u, -1); vis[root] = 1;
int dcm = root;
for(auto v : adj[dcm]){
if(vis[v]) continue;
int x = build(v);
par[x] = dcm;
}
return dcm;
}
int dp[nmax], ans = 0;
void update(int u){
int v = u;
while(u > 0){
dp[u] = min(dp[u], dist(u, v));
u = par[u];
}
}
void check(int u){
int ma = oo;
int v = u;
while(u > 0){
ma = min(ma, dist(u, v) + dp[u]);
u = par[u];
}
if(ma >= d){
update(v);
ans++;
}
}
int main(){
ios_base::sync_with_stdio(0);
cin.tie(0), cout.tie(0);
cin >> n >> d;
for(int i = 2, x; i <= n; ++i){
cin >> x;
++x;
adj[x].push_back(i);
adj[i].push_back(x);
}
dfs(1, -1);build(1);
memset(dp, 0x3f, sizeof dp);
for(int i = 1; i <= n; ++i) idx[i] = i;
for(int i = m; i >= 1; --i){
int u = tour[i];
rmq[i][0] = h[u];
st[u] = i;
}
for(int j = 1; j <= lg; ++j){
for(int i = 1; i + (1 << j) - 1 <= m; ++i){
rmq[i][j] = min(rmq[i][j - 1], rmq[i + (1 << (j - 1))][j - 1]);
}
}
sort(idx + 1, idx + 1 + n, [](int a, int b){
return h[a] > h[b];
});
for(int i = 1; i <= n; ++i){
int x = idx[i];
check(x);
}
cout << ans;
}
/*
*/
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
2 ms |
14940 KB |
Output is correct |
2 |
Correct |
2 ms |
14940 KB |
Output is correct |
3 |
Correct |
2 ms |
14940 KB |
Output is correct |
4 |
Correct |
2 ms |
14940 KB |
Output is correct |
5 |
Correct |
2 ms |
14940 KB |
Output is correct |
6 |
Correct |
2 ms |
14940 KB |
Output is correct |
7 |
Correct |
2 ms |
14940 KB |
Output is correct |
8 |
Correct |
2 ms |
14776 KB |
Output is correct |
9 |
Correct |
2 ms |
14940 KB |
Output is correct |
10 |
Correct |
2 ms |
14940 KB |
Output is correct |
11 |
Correct |
2 ms |
14940 KB |
Output is correct |
12 |
Correct |
3 ms |
14940 KB |
Output is correct |
13 |
Correct |
2 ms |
14940 KB |
Output is correct |
14 |
Correct |
2 ms |
14940 KB |
Output is correct |
15 |
Correct |
3 ms |
14940 KB |
Output is correct |
16 |
Correct |
3 ms |
14776 KB |
Output is correct |
17 |
Correct |
2 ms |
14940 KB |
Output is correct |
18 |
Correct |
2 ms |
14936 KB |
Output is correct |
19 |
Correct |
2 ms |
14940 KB |
Output is correct |
20 |
Correct |
2 ms |
14940 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
2 ms |
14940 KB |
Output is correct |
2 |
Correct |
2 ms |
14940 KB |
Output is correct |
3 |
Correct |
2 ms |
14940 KB |
Output is correct |
4 |
Correct |
2 ms |
14940 KB |
Output is correct |
5 |
Correct |
2 ms |
14940 KB |
Output is correct |
6 |
Correct |
2 ms |
14940 KB |
Output is correct |
7 |
Correct |
2 ms |
14940 KB |
Output is correct |
8 |
Correct |
2 ms |
14776 KB |
Output is correct |
9 |
Correct |
2 ms |
14940 KB |
Output is correct |
10 |
Correct |
2 ms |
14940 KB |
Output is correct |
11 |
Correct |
2 ms |
14940 KB |
Output is correct |
12 |
Correct |
3 ms |
14940 KB |
Output is correct |
13 |
Correct |
2 ms |
14940 KB |
Output is correct |
14 |
Correct |
2 ms |
14940 KB |
Output is correct |
15 |
Correct |
3 ms |
14940 KB |
Output is correct |
16 |
Correct |
3 ms |
14776 KB |
Output is correct |
17 |
Correct |
2 ms |
14940 KB |
Output is correct |
18 |
Correct |
2 ms |
14936 KB |
Output is correct |
19 |
Correct |
2 ms |
14940 KB |
Output is correct |
20 |
Correct |
2 ms |
14940 KB |
Output is correct |
21 |
Correct |
3 ms |
14940 KB |
Output is correct |
22 |
Correct |
3 ms |
14940 KB |
Output is correct |
23 |
Correct |
2 ms |
14940 KB |
Output is correct |
24 |
Correct |
2 ms |
14940 KB |
Output is correct |
25 |
Correct |
3 ms |
14940 KB |
Output is correct |
26 |
Correct |
3 ms |
15024 KB |
Output is correct |
27 |
Correct |
3 ms |
14940 KB |
Output is correct |
28 |
Correct |
3 ms |
14940 KB |
Output is correct |
29 |
Correct |
3 ms |
14940 KB |
Output is correct |
30 |
Correct |
3 ms |
14940 KB |
Output is correct |
31 |
Correct |
3 ms |
14940 KB |
Output is correct |
32 |
Correct |
3 ms |
14940 KB |
Output is correct |
33 |
Correct |
3 ms |
14940 KB |
Output is correct |
34 |
Correct |
3 ms |
14940 KB |
Output is correct |
35 |
Correct |
3 ms |
14940 KB |
Output is correct |
36 |
Correct |
3 ms |
14940 KB |
Output is correct |
37 |
Correct |
3 ms |
14940 KB |
Output is correct |
38 |
Correct |
3 ms |
14940 KB |
Output is correct |
39 |
Correct |
3 ms |
14940 KB |
Output is correct |
40 |
Correct |
3 ms |
14940 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
2 ms |
14940 KB |
Output is correct |
2 |
Correct |
2 ms |
14940 KB |
Output is correct |
3 |
Correct |
2 ms |
14940 KB |
Output is correct |
4 |
Correct |
2 ms |
14940 KB |
Output is correct |
5 |
Correct |
2 ms |
14940 KB |
Output is correct |
6 |
Correct |
2 ms |
14940 KB |
Output is correct |
7 |
Correct |
2 ms |
14940 KB |
Output is correct |
8 |
Correct |
2 ms |
14776 KB |
Output is correct |
9 |
Correct |
2 ms |
14940 KB |
Output is correct |
10 |
Correct |
2 ms |
14940 KB |
Output is correct |
11 |
Correct |
2 ms |
14940 KB |
Output is correct |
12 |
Correct |
3 ms |
14940 KB |
Output is correct |
13 |
Correct |
2 ms |
14940 KB |
Output is correct |
14 |
Correct |
2 ms |
14940 KB |
Output is correct |
15 |
Correct |
3 ms |
14940 KB |
Output is correct |
16 |
Correct |
3 ms |
14776 KB |
Output is correct |
17 |
Correct |
2 ms |
14940 KB |
Output is correct |
18 |
Correct |
2 ms |
14936 KB |
Output is correct |
19 |
Correct |
2 ms |
14940 KB |
Output is correct |
20 |
Correct |
2 ms |
14940 KB |
Output is correct |
21 |
Correct |
3 ms |
14940 KB |
Output is correct |
22 |
Correct |
3 ms |
14940 KB |
Output is correct |
23 |
Correct |
2 ms |
14940 KB |
Output is correct |
24 |
Correct |
2 ms |
14940 KB |
Output is correct |
25 |
Correct |
3 ms |
14940 KB |
Output is correct |
26 |
Correct |
3 ms |
15024 KB |
Output is correct |
27 |
Correct |
3 ms |
14940 KB |
Output is correct |
28 |
Correct |
3 ms |
14940 KB |
Output is correct |
29 |
Correct |
3 ms |
14940 KB |
Output is correct |
30 |
Correct |
3 ms |
14940 KB |
Output is correct |
31 |
Correct |
3 ms |
14940 KB |
Output is correct |
32 |
Correct |
3 ms |
14940 KB |
Output is correct |
33 |
Correct |
3 ms |
14940 KB |
Output is correct |
34 |
Correct |
3 ms |
14940 KB |
Output is correct |
35 |
Correct |
3 ms |
14940 KB |
Output is correct |
36 |
Correct |
3 ms |
14940 KB |
Output is correct |
37 |
Correct |
3 ms |
14940 KB |
Output is correct |
38 |
Correct |
3 ms |
14940 KB |
Output is correct |
39 |
Correct |
3 ms |
14940 KB |
Output is correct |
40 |
Correct |
3 ms |
14940 KB |
Output is correct |
41 |
Correct |
116 ms |
65228 KB |
Output is correct |
42 |
Correct |
99 ms |
43888 KB |
Output is correct |
43 |
Correct |
112 ms |
43892 KB |
Output is correct |
44 |
Correct |
79 ms |
43860 KB |
Output is correct |
45 |
Correct |
75 ms |
43856 KB |
Output is correct |
46 |
Correct |
241 ms |
66900 KB |
Output is correct |
47 |
Correct |
241 ms |
66900 KB |
Output is correct |
48 |
Correct |
245 ms |
66976 KB |
Output is correct |
49 |
Correct |
284 ms |
66980 KB |
Output is correct |
50 |
Correct |
56 ms |
44116 KB |
Output is correct |
51 |
Correct |
56 ms |
44112 KB |
Output is correct |
52 |
Correct |
63 ms |
44116 KB |
Output is correct |
53 |
Correct |
192 ms |
67416 KB |
Output is correct |
54 |
Correct |
169 ms |
67224 KB |
Output is correct |
55 |
Correct |
168 ms |
67196 KB |
Output is correct |
56 |
Correct |
5 ms |
14936 KB |
Output is correct |
57 |
Correct |
15 ms |
23384 KB |
Output is correct |
58 |
Correct |
93 ms |
50636 KB |
Output is correct |
59 |
Correct |
209 ms |
74708 KB |
Output is correct |
60 |
Correct |
125 ms |
66508 KB |
Output is correct |
61 |
Correct |
167 ms |
66548 KB |
Output is correct |