#include <bits/stdc++.h>
using namespace std;
using pii = pair <int, int>;
const int maxn = 2e5 + 10;
vector <int> g[maxn];
int dep[maxn];
bool done[maxn];
int n, D;
int anc[20][maxn];
const int logn = 19;
const int inf = 1e9 + 7;
int sub[maxn];
void flood(int x, int par, int dist) {
if(dist == 0) return ;
done[x] = true;
for(auto i : g[x]) {
if(i != par) {
flood(i, x, dist - 1);
}
}
}
void dfs(int x, int par) {
anc[0][x] = par == -1 ? 0 : par;
for(int i = 1; i <= logn; i++) {
anc[i][x] = anc[i - 1][anc[i - 1][x]];
}
for(auto i : g[x]) {
if(i != par) {
dep[i] = 1 + dep[x];
dfs(i, x);
}
}
}
int lca(int x, int y) {
if(dep[x] > dep[y]) swap(x, y);
for(int i = logn; i >= 0; i--) {
if(dep[y] - (1 << i) >= dep[x]) {
y = anc[i][y];
}
}
if(x == y) return x;
for(int i = logn; i >= 0; i--) {
if(anc[i][x] != anc[i][y]) {
x = anc[i][x];
y = anc[i][y];
}
}
return anc[0][y];
}
int distance(int p, int q) {
return dep[p] + dep[q] - 2 * dep[lca(p, q)];
}
int dad[maxn];
bool vis[maxn];
int near[maxn];
void subtree(int x, int par) {
sub[x] = 1;
for(auto i : g[x]) {
if(vis[i]) continue;
if(i != par) {
subtree(i, x);
sub[x] += sub[i];
}
}
}
int centroid(int x, int par, int range) {
for(auto i : g[x]) {
if(vis[i]) continue;
if(i != par) {
if(range < sub[i]) return centroid(i, x, range);
}
}
return x;
}
int createTree(int x) {
subtree(x, -1);
x = centroid(x, -1, sub[x] / 2);
vis[x] = true;
near[x] = inf;
for(auto i : g[x]) {
if(!vis[i]) {
dad[createTree(i)] = x;
}
}
return x;
}
void add(int x) {
int cur = x;
while(cur != -1) {
near[cur] = min(near[cur], distance(x, cur));
cur = dad[cur];
}
return ;
}
int closest(int x) {
int cur = x;
int opt = inf;
while(cur != -1) {
opt = min(opt, distance(x, cur) + near[cur]);
cur = dad[cur];
}
return opt;
}
int main() {
ios_base :: sync_with_stdio (false);
cin.tie(0);
cin >> n >> D;
for(int i = 1; i < n; i++) {
int x;
cin >> x;
g[x].emplace_back(i);
g[i].emplace_back(x);
}
dfs(0, -1);
// cout << distance(0, 3) << endl;
vector <pii> v;
for(int i = 0; i < n; i++) {
v.emplace_back(dep[i], i);
}
sort(v.begin(), v.end(), greater <pii> ());
dad[createTree(0)] = -1;
int ans = 0;
for(auto i : v) {
if(closest(i.second) < D) continue;
add(i.second);
++ans;
}
cout << ans << endl;
return 0;
}
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
7 ms |
5120 KB |
Output is correct |
2 |
Correct |
7 ms |
5120 KB |
Output is correct |
3 |
Correct |
7 ms |
5120 KB |
Output is correct |
4 |
Correct |
8 ms |
5120 KB |
Output is correct |
5 |
Correct |
8 ms |
5120 KB |
Output is correct |
6 |
Correct |
7 ms |
5248 KB |
Output is correct |
7 |
Correct |
7 ms |
5248 KB |
Output is correct |
8 |
Correct |
8 ms |
5120 KB |
Output is correct |
9 |
Correct |
7 ms |
5120 KB |
Output is correct |
10 |
Correct |
7 ms |
5248 KB |
Output is correct |
11 |
Correct |
7 ms |
5120 KB |
Output is correct |
12 |
Correct |
9 ms |
5120 KB |
Output is correct |
13 |
Correct |
7 ms |
5120 KB |
Output is correct |
14 |
Correct |
7 ms |
5248 KB |
Output is correct |
15 |
Correct |
7 ms |
5120 KB |
Output is correct |
16 |
Correct |
8 ms |
5248 KB |
Output is correct |
17 |
Correct |
8 ms |
5120 KB |
Output is correct |
18 |
Correct |
8 ms |
5120 KB |
Output is correct |
19 |
Correct |
7 ms |
5120 KB |
Output is correct |
20 |
Correct |
7 ms |
5120 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
7 ms |
5120 KB |
Output is correct |
2 |
Correct |
7 ms |
5120 KB |
Output is correct |
3 |
Correct |
7 ms |
5120 KB |
Output is correct |
4 |
Correct |
8 ms |
5120 KB |
Output is correct |
5 |
Correct |
8 ms |
5120 KB |
Output is correct |
6 |
Correct |
7 ms |
5248 KB |
Output is correct |
7 |
Correct |
7 ms |
5248 KB |
Output is correct |
8 |
Correct |
8 ms |
5120 KB |
Output is correct |
9 |
Correct |
7 ms |
5120 KB |
Output is correct |
10 |
Correct |
7 ms |
5248 KB |
Output is correct |
11 |
Correct |
7 ms |
5120 KB |
Output is correct |
12 |
Correct |
9 ms |
5120 KB |
Output is correct |
13 |
Correct |
7 ms |
5120 KB |
Output is correct |
14 |
Correct |
7 ms |
5248 KB |
Output is correct |
15 |
Correct |
7 ms |
5120 KB |
Output is correct |
16 |
Correct |
8 ms |
5248 KB |
Output is correct |
17 |
Correct |
8 ms |
5120 KB |
Output is correct |
18 |
Correct |
8 ms |
5120 KB |
Output is correct |
19 |
Correct |
7 ms |
5120 KB |
Output is correct |
20 |
Correct |
7 ms |
5120 KB |
Output is correct |
21 |
Correct |
9 ms |
5504 KB |
Output is correct |
22 |
Correct |
8 ms |
5248 KB |
Output is correct |
23 |
Correct |
7 ms |
5248 KB |
Output is correct |
24 |
Correct |
7 ms |
5248 KB |
Output is correct |
25 |
Correct |
8 ms |
5248 KB |
Output is correct |
26 |
Correct |
8 ms |
5248 KB |
Output is correct |
27 |
Correct |
8 ms |
5376 KB |
Output is correct |
28 |
Correct |
9 ms |
5376 KB |
Output is correct |
29 |
Correct |
8 ms |
5376 KB |
Output is correct |
30 |
Correct |
9 ms |
5376 KB |
Output is correct |
31 |
Correct |
10 ms |
5376 KB |
Output is correct |
32 |
Correct |
8 ms |
5408 KB |
Output is correct |
33 |
Correct |
8 ms |
5376 KB |
Output is correct |
34 |
Correct |
8 ms |
5376 KB |
Output is correct |
35 |
Correct |
8 ms |
5376 KB |
Output is correct |
36 |
Correct |
8 ms |
5376 KB |
Output is correct |
37 |
Correct |
8 ms |
5376 KB |
Output is correct |
38 |
Correct |
8 ms |
5376 KB |
Output is correct |
39 |
Correct |
9 ms |
5504 KB |
Output is correct |
40 |
Correct |
9 ms |
5504 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
7 ms |
5120 KB |
Output is correct |
2 |
Correct |
7 ms |
5120 KB |
Output is correct |
3 |
Correct |
7 ms |
5120 KB |
Output is correct |
4 |
Correct |
8 ms |
5120 KB |
Output is correct |
5 |
Correct |
8 ms |
5120 KB |
Output is correct |
6 |
Correct |
7 ms |
5248 KB |
Output is correct |
7 |
Correct |
7 ms |
5248 KB |
Output is correct |
8 |
Correct |
8 ms |
5120 KB |
Output is correct |
9 |
Correct |
7 ms |
5120 KB |
Output is correct |
10 |
Correct |
7 ms |
5248 KB |
Output is correct |
11 |
Correct |
7 ms |
5120 KB |
Output is correct |
12 |
Correct |
9 ms |
5120 KB |
Output is correct |
13 |
Correct |
7 ms |
5120 KB |
Output is correct |
14 |
Correct |
7 ms |
5248 KB |
Output is correct |
15 |
Correct |
7 ms |
5120 KB |
Output is correct |
16 |
Correct |
8 ms |
5248 KB |
Output is correct |
17 |
Correct |
8 ms |
5120 KB |
Output is correct |
18 |
Correct |
8 ms |
5120 KB |
Output is correct |
19 |
Correct |
7 ms |
5120 KB |
Output is correct |
20 |
Correct |
7 ms |
5120 KB |
Output is correct |
21 |
Correct |
9 ms |
5504 KB |
Output is correct |
22 |
Correct |
8 ms |
5248 KB |
Output is correct |
23 |
Correct |
7 ms |
5248 KB |
Output is correct |
24 |
Correct |
7 ms |
5248 KB |
Output is correct |
25 |
Correct |
8 ms |
5248 KB |
Output is correct |
26 |
Correct |
8 ms |
5248 KB |
Output is correct |
27 |
Correct |
8 ms |
5376 KB |
Output is correct |
28 |
Correct |
9 ms |
5376 KB |
Output is correct |
29 |
Correct |
8 ms |
5376 KB |
Output is correct |
30 |
Correct |
9 ms |
5376 KB |
Output is correct |
31 |
Correct |
10 ms |
5376 KB |
Output is correct |
32 |
Correct |
8 ms |
5408 KB |
Output is correct |
33 |
Correct |
8 ms |
5376 KB |
Output is correct |
34 |
Correct |
8 ms |
5376 KB |
Output is correct |
35 |
Correct |
8 ms |
5376 KB |
Output is correct |
36 |
Correct |
8 ms |
5376 KB |
Output is correct |
37 |
Correct |
8 ms |
5376 KB |
Output is correct |
38 |
Correct |
8 ms |
5376 KB |
Output is correct |
39 |
Correct |
9 ms |
5504 KB |
Output is correct |
40 |
Correct |
9 ms |
5504 KB |
Output is correct |
41 |
Correct |
131 ms |
31080 KB |
Output is correct |
42 |
Correct |
240 ms |
19436 KB |
Output is correct |
43 |
Correct |
184 ms |
19356 KB |
Output is correct |
44 |
Correct |
180 ms |
19308 KB |
Output is correct |
45 |
Correct |
182 ms |
19308 KB |
Output is correct |
46 |
Correct |
614 ms |
33456 KB |
Output is correct |
47 |
Correct |
458 ms |
33512 KB |
Output is correct |
48 |
Correct |
506 ms |
33472 KB |
Output is correct |
49 |
Correct |
446 ms |
33384 KB |
Output is correct |
50 |
Correct |
116 ms |
19692 KB |
Output is correct |
51 |
Correct |
130 ms |
19688 KB |
Output is correct |
52 |
Correct |
124 ms |
19692 KB |
Output is correct |
53 |
Correct |
346 ms |
33764 KB |
Output is correct |
54 |
Correct |
299 ms |
33872 KB |
Output is correct |
55 |
Correct |
275 ms |
33764 KB |
Output is correct |
56 |
Correct |
12 ms |
5632 KB |
Output is correct |
57 |
Correct |
40 ms |
9472 KB |
Output is correct |
58 |
Correct |
214 ms |
24940 KB |
Output is correct |
59 |
Correct |
623 ms |
39524 KB |
Output is correct |
60 |
Correct |
159 ms |
32748 KB |
Output is correct |
61 |
Correct |
273 ms |
31980 KB |
Output is correct |