#include <bits/stdc++.h>
using namespace std;
const int kN = 2e5;
const int kLog = 20;
const int kInf = 1e9;
int dep[kN], tin[kN];
vector<int> adj[kN], rmq[kLog];
void dfs(int u, int p = -1) {
tin[u] = rmq[0].size();
rmq[0].emplace_back(u);
for(const auto &v: adj[u]) if(v != p) {
dep[v] = dep[u] + 1;
dfs(v, u);
rmq[0].emplace_back(u);
}
}
int minNode(int u, int v) {
if(dep[u] < dep[v]) return u;
return v;
}
int lca(int u, int v) {
int l = tin[u], r = tin[v];
if(l > r) swap(l, r);
int lg = __lg(r - l + 1);
return minNode(rmq[lg][l], rmq[lg][r - (1 << lg) + 1]);
}
int dist(int u, int v) {
return dep[u] + dep[v] - 2 * dep[lca(u, v)];
}
void minSelf(int &x, int y) {
if(y < x) {
x = y;
}
}
int sz[kN];
bitset<kN> rem;
void findSizes(int u, int p = -1) {
sz[u] = 1;
for(const auto &v: adj[u]) if(!rem[v] && v != p) {
findSizes(v, u);
sz[u] += sz[v];
}
}
int findCentroid(int u, int desired, int p = -1) {
for(const auto &v: adj[u]) if(!rem[v] && v != p && sz[v] > desired) {
return findCentroid(v, desired, u);
}
return u;
}
int up[kN], best[kN];
void buildTree(int u, int p = -1) {
findSizes(u);
int c = findCentroid(u, sz[u] >> 1);
rem[c] = true;
up[c] = p;
for(const auto &v: adj[c]) if(!rem[v]) {
buildTree(v, c);
}
}
int findClosest(int u) {
int res = kInf, v = u;
while(v != -1) {
minSelf(res, best[v] + dist(u, v));
v = up[v];
}
return res;
}
void updateClosest(int u) {
int v = u;
while(v != -1) {
minSelf(best[v], dist(u, v));
v = up[v];
}
}
int main() {
cin.tie(nullptr)->sync_with_stdio(false);
int n, d;
cin >> n >> d;
for(int i = 1; i < n; i++) {
int x;
cin >> x;
adj[x].emplace_back(i);
adj[i].emplace_back(x);
}
rmq[0].reserve(n << 1);
dfs(0);
for(int i = 1; (1 << i) < n << 1; i++) {
for(int j = 0; j + (1 << i) - 1 < 2 * n - 1; j++) {
rmq[i].emplace_back(minNode(rmq[i - 1][j], rmq[i - 1][j + (1 << (i - 1))]));
}
}
vector<int> ord(n);
iota(ord.begin(), ord.end(), 0);
sort(ord.begin(), ord.end(), [&] (int u, int v) {
return dep[u] > dep[v];
});
for(int i = 0; i < n; i++) {
best[i] = kInf;
up[i] = -1;
}
buildTree(0);
int ans = 0;
for(const auto &u: ord) {
int closest = findClosest(u);
if(closest >= d) {
ans++;
updateClosest(u);
}
}
cout << ans;
return 0;
}
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
1 ms |
8540 KB |
Output is correct |
2 |
Correct |
2 ms |
8540 KB |
Output is correct |
3 |
Correct |
2 ms |
8540 KB |
Output is correct |
4 |
Correct |
1 ms |
8540 KB |
Output is correct |
5 |
Correct |
1 ms |
8540 KB |
Output is correct |
6 |
Correct |
1 ms |
8540 KB |
Output is correct |
7 |
Correct |
1 ms |
8540 KB |
Output is correct |
8 |
Correct |
2 ms |
8536 KB |
Output is correct |
9 |
Correct |
2 ms |
8536 KB |
Output is correct |
10 |
Correct |
2 ms |
8540 KB |
Output is correct |
11 |
Correct |
1 ms |
8540 KB |
Output is correct |
12 |
Correct |
1 ms |
8540 KB |
Output is correct |
13 |
Correct |
2 ms |
8584 KB |
Output is correct |
14 |
Correct |
1 ms |
8540 KB |
Output is correct |
15 |
Correct |
2 ms |
8540 KB |
Output is correct |
16 |
Correct |
2 ms |
8540 KB |
Output is correct |
17 |
Correct |
2 ms |
8540 KB |
Output is correct |
18 |
Correct |
2 ms |
8540 KB |
Output is correct |
19 |
Correct |
1 ms |
8540 KB |
Output is correct |
20 |
Correct |
1 ms |
8540 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
1 ms |
8540 KB |
Output is correct |
2 |
Correct |
2 ms |
8540 KB |
Output is correct |
3 |
Correct |
2 ms |
8540 KB |
Output is correct |
4 |
Correct |
1 ms |
8540 KB |
Output is correct |
5 |
Correct |
1 ms |
8540 KB |
Output is correct |
6 |
Correct |
1 ms |
8540 KB |
Output is correct |
7 |
Correct |
1 ms |
8540 KB |
Output is correct |
8 |
Correct |
2 ms |
8536 KB |
Output is correct |
9 |
Correct |
2 ms |
8536 KB |
Output is correct |
10 |
Correct |
2 ms |
8540 KB |
Output is correct |
11 |
Correct |
1 ms |
8540 KB |
Output is correct |
12 |
Correct |
1 ms |
8540 KB |
Output is correct |
13 |
Correct |
2 ms |
8584 KB |
Output is correct |
14 |
Correct |
1 ms |
8540 KB |
Output is correct |
15 |
Correct |
2 ms |
8540 KB |
Output is correct |
16 |
Correct |
2 ms |
8540 KB |
Output is correct |
17 |
Correct |
2 ms |
8540 KB |
Output is correct |
18 |
Correct |
2 ms |
8540 KB |
Output is correct |
19 |
Correct |
1 ms |
8540 KB |
Output is correct |
20 |
Correct |
1 ms |
8540 KB |
Output is correct |
21 |
Correct |
2 ms |
8796 KB |
Output is correct |
22 |
Correct |
2 ms |
8540 KB |
Output is correct |
23 |
Correct |
2 ms |
8540 KB |
Output is correct |
24 |
Correct |
2 ms |
8540 KB |
Output is correct |
25 |
Correct |
2 ms |
8796 KB |
Output is correct |
26 |
Correct |
2 ms |
8792 KB |
Output is correct |
27 |
Correct |
2 ms |
8796 KB |
Output is correct |
28 |
Correct |
2 ms |
8796 KB |
Output is correct |
29 |
Correct |
3 ms |
8796 KB |
Output is correct |
30 |
Correct |
2 ms |
8796 KB |
Output is correct |
31 |
Correct |
2 ms |
8796 KB |
Output is correct |
32 |
Correct |
2 ms |
8796 KB |
Output is correct |
33 |
Correct |
2 ms |
8796 KB |
Output is correct |
34 |
Correct |
2 ms |
8796 KB |
Output is correct |
35 |
Correct |
2 ms |
8796 KB |
Output is correct |
36 |
Correct |
2 ms |
8796 KB |
Output is correct |
37 |
Correct |
2 ms |
8792 KB |
Output is correct |
38 |
Correct |
2 ms |
8792 KB |
Output is correct |
39 |
Correct |
2 ms |
8796 KB |
Output is correct |
40 |
Correct |
3 ms |
8796 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
1 ms |
8540 KB |
Output is correct |
2 |
Correct |
2 ms |
8540 KB |
Output is correct |
3 |
Correct |
2 ms |
8540 KB |
Output is correct |
4 |
Correct |
1 ms |
8540 KB |
Output is correct |
5 |
Correct |
1 ms |
8540 KB |
Output is correct |
6 |
Correct |
1 ms |
8540 KB |
Output is correct |
7 |
Correct |
1 ms |
8540 KB |
Output is correct |
8 |
Correct |
2 ms |
8536 KB |
Output is correct |
9 |
Correct |
2 ms |
8536 KB |
Output is correct |
10 |
Correct |
2 ms |
8540 KB |
Output is correct |
11 |
Correct |
1 ms |
8540 KB |
Output is correct |
12 |
Correct |
1 ms |
8540 KB |
Output is correct |
13 |
Correct |
2 ms |
8584 KB |
Output is correct |
14 |
Correct |
1 ms |
8540 KB |
Output is correct |
15 |
Correct |
2 ms |
8540 KB |
Output is correct |
16 |
Correct |
2 ms |
8540 KB |
Output is correct |
17 |
Correct |
2 ms |
8540 KB |
Output is correct |
18 |
Correct |
2 ms |
8540 KB |
Output is correct |
19 |
Correct |
1 ms |
8540 KB |
Output is correct |
20 |
Correct |
1 ms |
8540 KB |
Output is correct |
21 |
Correct |
2 ms |
8796 KB |
Output is correct |
22 |
Correct |
2 ms |
8540 KB |
Output is correct |
23 |
Correct |
2 ms |
8540 KB |
Output is correct |
24 |
Correct |
2 ms |
8540 KB |
Output is correct |
25 |
Correct |
2 ms |
8796 KB |
Output is correct |
26 |
Correct |
2 ms |
8792 KB |
Output is correct |
27 |
Correct |
2 ms |
8796 KB |
Output is correct |
28 |
Correct |
2 ms |
8796 KB |
Output is correct |
29 |
Correct |
3 ms |
8796 KB |
Output is correct |
30 |
Correct |
2 ms |
8796 KB |
Output is correct |
31 |
Correct |
2 ms |
8796 KB |
Output is correct |
32 |
Correct |
2 ms |
8796 KB |
Output is correct |
33 |
Correct |
2 ms |
8796 KB |
Output is correct |
34 |
Correct |
2 ms |
8796 KB |
Output is correct |
35 |
Correct |
2 ms |
8796 KB |
Output is correct |
36 |
Correct |
2 ms |
8796 KB |
Output is correct |
37 |
Correct |
2 ms |
8792 KB |
Output is correct |
38 |
Correct |
2 ms |
8792 KB |
Output is correct |
39 |
Correct |
2 ms |
8796 KB |
Output is correct |
40 |
Correct |
3 ms |
8796 KB |
Output is correct |
41 |
Correct |
81 ms |
43136 KB |
Output is correct |
42 |
Correct |
80 ms |
26184 KB |
Output is correct |
43 |
Correct |
77 ms |
26220 KB |
Output is correct |
44 |
Correct |
77 ms |
26068 KB |
Output is correct |
45 |
Correct |
73 ms |
26192 KB |
Output is correct |
46 |
Correct |
182 ms |
45360 KB |
Output is correct |
47 |
Correct |
206 ms |
45376 KB |
Output is correct |
48 |
Correct |
177 ms |
45480 KB |
Output is correct |
49 |
Correct |
176 ms |
45340 KB |
Output is correct |
50 |
Correct |
48 ms |
26440 KB |
Output is correct |
51 |
Correct |
54 ms |
26428 KB |
Output is correct |
52 |
Correct |
46 ms |
26448 KB |
Output is correct |
53 |
Correct |
127 ms |
45936 KB |
Output is correct |
54 |
Correct |
111 ms |
45808 KB |
Output is correct |
55 |
Correct |
112 ms |
45800 KB |
Output is correct |
56 |
Correct |
3 ms |
9052 KB |
Output is correct |
57 |
Correct |
14 ms |
13272 KB |
Output is correct |
58 |
Correct |
76 ms |
31768 KB |
Output is correct |
59 |
Correct |
182 ms |
52548 KB |
Output is correct |
60 |
Correct |
82 ms |
44640 KB |
Output is correct |
61 |
Correct |
122 ms |
43716 KB |
Output is correct |