Baltic OI '17 P6 - Cat in a tree

View as PDF

Submit solution

Points: 15 (partial)
Time limit: 1.0s
Memory limit: 1G

Problem types
Allowed languages
Ada, Assembly, Awk, Brain****, C, C#, C++, COBOL, CommonLisp, D, Dart, F#, Forth, Fortran, Go, Groovy, Haskell, Intercal, Java, JS, Kotlin, Lisp, Lua, Nim, ObjC, OCaml, Octave, Pascal, Perl, PHP, Pike, Prolog, Python, Racket, Ruby, Rust, Scala, Scheme, Sed, Swift, TCL, Text, Turing, VB, Zig
Baltic Olympiad in Informatics: 2017 Day 2, Problem 3

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.

Input Specification

First line has two integers, N and D. The 0th node is the root node of the tree. Then follows N-1 lines, the ith of which contain a single integer x_i with 0 \leq x_i < i (starting with i= 1). This means that node x_i is connected to node i.


We always have 1 \le N, D\le2\times 10^5. For subcases, the inputs have these further restrictions:

  • Group 1: 11 points N \le 18
  • Group 2: 40 points N \le 1\,500
  • Group 3: 49 points No further restrictions.

Output Specification

Output should contain one integer: the maximum number of nodes that can be marked.

Sample Input 1

4 3

Sample Output 1


Sample Input 2

3 1000

Sample Output 2



There are no comments at the moment.