Another Contest 5 Problem 5 - Another Cheese Problem

View as PDF

Submit solution


Points: 12
Time limit: 1.4s
Memory limit: 256M

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

After a long day of being a goat farmer, Tudor finally returns to an old hobby of his - baking cheese.

Tudor's recipe requires N operations to be performed. The operations happen to form a directed tree, where operation a_i may depend on some other operations to be performed first. Operation 1 is guaranteed to be the last operation to perform and there will be no cyclic dependencies.

Each operation will generate some intermediate result in the process of baking cheese that needs to be stored in a bowl. When an operation that depends on others to be done first is to be performed, Tudor will take all of the bowls with those intermediate results, grab a new bowl, and mix the intermediate results in the new bowl. After that, the other bowls may be cleaned and reused in later operations.

Compute the minimum number of bowls Tudor needs to bake cheese.

Constraints

2 \le N \le 10^6

a_i < i

Input Specification

The first line contains a single positive integer, N.

Each of the next N-1 lines contain the integers a_2 through a_N in order, one per line. Operation a_i depends directly on operation i to be completed first.

Output Specification

Output the minimum number of bowls that Tudor needs.

Sample Input

5
1
1
2
2

Sample Output

3

Sample Explanation

Below, we provide a diagram showing the dependencies on operations explicitly. We can show that 2 bowls is not sufficient to perform all the operations. If we have bowls A, B, and C, then the following steps show that 3 bowls are sufficient to perform all the operations.

  1. Perform operation 5 and store the result in bowl A.
  2. Perform operation 4 and store the result in bowl B.
  3. Perform operation 2, using bowls A and B, and store the result in bowl C.
  4. Clean bowls A and B.
  5. Perform operation 3 and store the result in bowl B.
  6. Perform operation 1, using bowls B and C, and store the result in bowl A.
    1
   / \
  2   3
 / \
4   5

Comments

There are no comments at the moment.