#include <bits/stdc++.h>
using namespace std;
int main() {
ios::sync_with_stdio(0);
cin.tie(0);
int N, D;
cin >> N >> D;
vector<vector<int>> adj(N);
for (int i = 1; i < N; i++) {
int p;
cin >> p;
adj[p].emplace_back(i);
}
// Solution:
//
// Similar to: https://atcoder.jp/contests/xmascon16noon/tasks/xmascon16_h
//
// For each node, we save the maximum number of picked nodes, which
// also maximizes the minimum distance to current node. We additionally save the
// number of nodes which has that maximum minimum distance.
//
// Consider 2 children of current node. Assume from child[1], we pick 1 node,
// where the distance is a, and from the other child, we pick 2 nodes, where
// the distance to current node is p + x and q + x (distance between the 2 nodes
// is p + q).
//
// Then, we have p + q >= K. Moreover, if:
// a + x + p < K
// a + x + q < K
// p + q >= K
// Implies:
// 2a + 2x + (p + q) < 2K
// 2a + 2x < K
// a + x < K / 2
//
// Then, since p + q >= K -> max(p, q) >= K / 2
//
// So, a + x + p < K and a + x + q < K only happens when:
// p = q = K / 2
// a + x < K / 2
//
// If p > K / 2, then a + x + p >= K, so we using the
// explained data (maximum picked, distance to picked,
// count nodes with that distance) is enough.
//
// We can also note that, since p, q is from same child,
// then x >= 1. So, this a + x + p < K and a + x + q < K
// case can only happen when a < K / 2 - 1. But in this case,
// we can just not pick a to preserve the condition (by picking
// p and q) instead. So, we only need to keep the minimum distance
// instead.
//
// Time complexity: O(N).
int ans = 0;
const auto Dfs = [&](const auto &self, int u) -> int {
ans += 1; // pick current node
int dist = 0;
for (auto v : adj[u]) {
int other = self(self, v) + 1;
if (dist + other < D) {
ans -= 1; // we only need to decrease 1, by lemma above
dist = max(dist, other);
} else {
dist = min(dist, other);
}
}
return dist;
};
Dfs(Dfs, 0);
cout << ans << '\n';
return 0;
}
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
1 ms |
204 KB |
Output is correct |
2 |
Correct |
1 ms |
204 KB |
Output is correct |
3 |
Correct |
1 ms |
204 KB |
Output is correct |
4 |
Correct |
1 ms |
204 KB |
Output is correct |
5 |
Correct |
1 ms |
204 KB |
Output is correct |
6 |
Correct |
1 ms |
204 KB |
Output is correct |
7 |
Correct |
1 ms |
204 KB |
Output is correct |
8 |
Correct |
1 ms |
204 KB |
Output is correct |
9 |
Correct |
1 ms |
204 KB |
Output is correct |
10 |
Correct |
1 ms |
204 KB |
Output is correct |
11 |
Correct |
1 ms |
204 KB |
Output is correct |
12 |
Correct |
1 ms |
204 KB |
Output is correct |
13 |
Correct |
1 ms |
204 KB |
Output is correct |
14 |
Correct |
1 ms |
204 KB |
Output is correct |
15 |
Correct |
1 ms |
312 KB |
Output is correct |
16 |
Correct |
1 ms |
204 KB |
Output is correct |
17 |
Correct |
1 ms |
256 KB |
Output is correct |
18 |
Correct |
1 ms |
312 KB |
Output is correct |
19 |
Correct |
1 ms |
204 KB |
Output is correct |
20 |
Correct |
1 ms |
204 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
1 ms |
204 KB |
Output is correct |
2 |
Correct |
1 ms |
204 KB |
Output is correct |
3 |
Correct |
1 ms |
204 KB |
Output is correct |
4 |
Correct |
1 ms |
204 KB |
Output is correct |
5 |
Correct |
1 ms |
204 KB |
Output is correct |
6 |
Correct |
1 ms |
204 KB |
Output is correct |
7 |
Correct |
1 ms |
204 KB |
Output is correct |
8 |
Correct |
1 ms |
204 KB |
Output is correct |
9 |
Correct |
1 ms |
204 KB |
Output is correct |
10 |
Correct |
1 ms |
204 KB |
Output is correct |
11 |
Correct |
1 ms |
204 KB |
Output is correct |
12 |
Correct |
1 ms |
204 KB |
Output is correct |
13 |
Correct |
1 ms |
204 KB |
Output is correct |
14 |
Correct |
1 ms |
204 KB |
Output is correct |
15 |
Correct |
1 ms |
312 KB |
Output is correct |
16 |
Correct |
1 ms |
204 KB |
Output is correct |
17 |
Correct |
1 ms |
256 KB |
Output is correct |
18 |
Correct |
1 ms |
312 KB |
Output is correct |
19 |
Correct |
1 ms |
204 KB |
Output is correct |
20 |
Correct |
1 ms |
204 KB |
Output is correct |
21 |
Correct |
2 ms |
332 KB |
Output is correct |
22 |
Correct |
1 ms |
332 KB |
Output is correct |
23 |
Correct |
1 ms |
332 KB |
Output is correct |
24 |
Correct |
1 ms |
332 KB |
Output is correct |
25 |
Correct |
1 ms |
332 KB |
Output is correct |
26 |
Correct |
1 ms |
332 KB |
Output is correct |
27 |
Correct |
1 ms |
316 KB |
Output is correct |
28 |
Correct |
1 ms |
320 KB |
Output is correct |
29 |
Correct |
1 ms |
332 KB |
Output is correct |
30 |
Correct |
1 ms |
332 KB |
Output is correct |
31 |
Correct |
1 ms |
332 KB |
Output is correct |
32 |
Correct |
1 ms |
332 KB |
Output is correct |
33 |
Correct |
1 ms |
332 KB |
Output is correct |
34 |
Correct |
1 ms |
332 KB |
Output is correct |
35 |
Correct |
1 ms |
332 KB |
Output is correct |
36 |
Correct |
1 ms |
332 KB |
Output is correct |
37 |
Correct |
1 ms |
332 KB |
Output is correct |
38 |
Correct |
1 ms |
332 KB |
Output is correct |
39 |
Correct |
1 ms |
332 KB |
Output is correct |
40 |
Correct |
1 ms |
332 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
1 ms |
204 KB |
Output is correct |
2 |
Correct |
1 ms |
204 KB |
Output is correct |
3 |
Correct |
1 ms |
204 KB |
Output is correct |
4 |
Correct |
1 ms |
204 KB |
Output is correct |
5 |
Correct |
1 ms |
204 KB |
Output is correct |
6 |
Correct |
1 ms |
204 KB |
Output is correct |
7 |
Correct |
1 ms |
204 KB |
Output is correct |
8 |
Correct |
1 ms |
204 KB |
Output is correct |
9 |
Correct |
1 ms |
204 KB |
Output is correct |
10 |
Correct |
1 ms |
204 KB |
Output is correct |
11 |
Correct |
1 ms |
204 KB |
Output is correct |
12 |
Correct |
1 ms |
204 KB |
Output is correct |
13 |
Correct |
1 ms |
204 KB |
Output is correct |
14 |
Correct |
1 ms |
204 KB |
Output is correct |
15 |
Correct |
1 ms |
312 KB |
Output is correct |
16 |
Correct |
1 ms |
204 KB |
Output is correct |
17 |
Correct |
1 ms |
256 KB |
Output is correct |
18 |
Correct |
1 ms |
312 KB |
Output is correct |
19 |
Correct |
1 ms |
204 KB |
Output is correct |
20 |
Correct |
1 ms |
204 KB |
Output is correct |
21 |
Correct |
2 ms |
332 KB |
Output is correct |
22 |
Correct |
1 ms |
332 KB |
Output is correct |
23 |
Correct |
1 ms |
332 KB |
Output is correct |
24 |
Correct |
1 ms |
332 KB |
Output is correct |
25 |
Correct |
1 ms |
332 KB |
Output is correct |
26 |
Correct |
1 ms |
332 KB |
Output is correct |
27 |
Correct |
1 ms |
316 KB |
Output is correct |
28 |
Correct |
1 ms |
320 KB |
Output is correct |
29 |
Correct |
1 ms |
332 KB |
Output is correct |
30 |
Correct |
1 ms |
332 KB |
Output is correct |
31 |
Correct |
1 ms |
332 KB |
Output is correct |
32 |
Correct |
1 ms |
332 KB |
Output is correct |
33 |
Correct |
1 ms |
332 KB |
Output is correct |
34 |
Correct |
1 ms |
332 KB |
Output is correct |
35 |
Correct |
1 ms |
332 KB |
Output is correct |
36 |
Correct |
1 ms |
332 KB |
Output is correct |
37 |
Correct |
1 ms |
332 KB |
Output is correct |
38 |
Correct |
1 ms |
332 KB |
Output is correct |
39 |
Correct |
1 ms |
332 KB |
Output is correct |
40 |
Correct |
1 ms |
332 KB |
Output is correct |
41 |
Correct |
38 ms |
9572 KB |
Output is correct |
42 |
Correct |
25 ms |
4812 KB |
Output is correct |
43 |
Correct |
25 ms |
4804 KB |
Output is correct |
44 |
Correct |
23 ms |
4840 KB |
Output is correct |
45 |
Correct |
24 ms |
4840 KB |
Output is correct |
46 |
Correct |
61 ms |
9348 KB |
Output is correct |
47 |
Correct |
57 ms |
9348 KB |
Output is correct |
48 |
Correct |
57 ms |
9284 KB |
Output is correct |
49 |
Correct |
57 ms |
9368 KB |
Output is correct |
50 |
Correct |
14 ms |
3532 KB |
Output is correct |
51 |
Correct |
15 ms |
3600 KB |
Output is correct |
52 |
Correct |
14 ms |
3636 KB |
Output is correct |
53 |
Correct |
29 ms |
6852 KB |
Output is correct |
54 |
Correct |
35 ms |
6832 KB |
Output is correct |
55 |
Correct |
28 ms |
6860 KB |
Output is correct |
56 |
Correct |
1 ms |
332 KB |
Output is correct |
57 |
Correct |
5 ms |
1956 KB |
Output is correct |
58 |
Correct |
21 ms |
8136 KB |
Output is correct |
59 |
Correct |
46 ms |
11756 KB |
Output is correct |
60 |
Correct |
46 ms |
10056 KB |
Output is correct |
61 |
Correct |
55 ms |
9800 KB |
Output is correct |