P8744 [Lanqiao Cup 2021 NOI Qualifier A] Left Child Right Sibling

For a multiway tree, we can convert it into a binary tree using the “left child right sibling” representation. If we consider the children of each node to be unordered, then the resulting binary tree may not be unique. In other words, for each node, we may choose any child as its left child, and connect the remaining children as right siblings in any order. Given a multiway tree with $N$ nodes, numbered from $1$ to $N$, where node $1$ is the root, and the index of each node’s parent is smaller than the node’s own index, compute the maximum possible height of the binary tree obtained by the “left child right sibling” representation. (A tree with only the root node has height $0$.) For example, the following multiway tree:  may have the following $3$ different “left child right sibling” representations (only $3$ are listed here, not all of them):  The last one has the greatest height, which is $4$.

The first line contains an integer $N$. The next $N - 1$ lines each contain an integer, in order giving the parent index of nodes $2$ to $N$.

Output one integer representing the answer.

For $30\%$ of the test cases, $1 \leq N \leq 20$. For all test cases, $1 \leq N \leq 10^5$. Lanqiao Cup 2021, first round, provincial contest, Group A, Problem H. Translated by ChatGPT 5