시간 제한 | 메모리 제한 | 제출 | 정답 | 맞힌 사람 | 정답 비율 |
---|---|---|---|---|---|
1 초 | 512 MB | 52 | 20 | 19 | 37.255% |
A cat lives in a tree that has N nodes. She will demarcate her territory by “marking” some of the tree nodes. Marked nodes may not be closer to each other than distance D. Find the maximum number of nodes that the cat can mark.
First line has two integers, N and D. The 0’th node is the root node of the tree. Then follows N − 1 lines, the i-th of which contain a single integer xi with 0 ≤ xi < i (starting with i = 1). This means that node xi is connected to node i.
Output should contain one integer: the maximum number of nodes that can be marked.
We always have 1 ≤ N, D ≤ 2 · 105. For subcases, the inputs have these further restrictions.
번호 | 배점 | 제한 |
---|---|---|
1 | 11 | N ≤ 18 |
2 | 40 | N ≤ 1 500 |
3 | 49 | No further restrictions. |
4 3 0 0 1
2
3 1000 0 0
1