[Solution] Hanging Hearts Codeforces Solution

E. Hanging Hearts

time limit per test

1 second

memory limit per test

256 megabytes

input

standard input

output

standard output

Pak Chanek has 𝑛$n$ blank heart-shaped cards. Card 1$1$ is attached directly to the wall while each of the other cards is hanging onto exactly one other card by a piece of string. Specifically, card 𝑖$i$ (𝑖>1$i>1$) is hanging onto card 𝑝𝑖$p_i$ (𝑝𝑖<𝑖$p_i<i$).

In the very beginning, Pak Chanek must write one integer number on each card. He does this by choosing any permutation 𝑎$a$ of [1,2,…,𝑛]$[1,2,\dots ,n]$. Then, the number written on card 𝑖$i$ is 𝑎𝑖$a_i$.

After that, Pak Chanek must do the following operation 𝑛$n$ times while maintaining a sequence 𝑠$s$ (which is initially empty):

1. Choose a card 𝑥$x$ such that no other cards are hanging onto it.
2. Append the number written on card 𝑥$x$ to the end of 𝑠$s$.
3. If 𝑥≠1$x\ne 1$ and the number on card 𝑝𝑥$p_x$ is larger than the number on card 𝑥$x$, replace the number on card 𝑝𝑥$p_x$ with the number on card 𝑥$x$.
4. Remove card 𝑥$x$.

After that, Pak Chanek will have a sequence 𝑠$s$ with 𝑛$n$ elements. What is the maximum length of the longest non-decreasing subsequence†${}^{†}$ of 𝑠$s$ at the end if Pak Chanek does all the steps optimally?

†${}^{†}$ A sequence 𝑏$b$ is a subsequence of a sequence 𝑐$c$ if 𝑏$b$ can be obtained from 𝑐$c$ by deletion of several (possibly, zero or all) elements. For example, [3,1]$[3,1]$ is a subsequence of [3,2,1]$[3,2,1]$, [4,3,1]$[4,3,1]$ and [3,1]$[3,1]$, but not [1,3,3,7]$[1,3,3,7]$ and [3,10,4]$[3,10,4]$.

Input

The first line contains a single integer 𝑛$n$ (2≤𝑛≤105$2\le n\le {10}^5$) — the number of heart-shaped cards.

The second line contains 𝑛−1$n-1$ integers 𝑝2,𝑝3,…,𝑝𝑛$p_2,p_3,\dots ,p_n$ (1≤𝑝𝑖<𝑖$1\le p_i<i$) describing which card that each card hangs onto.

Output

Print a single integer — the maximum length of the longest non-decreasing subsequence of 𝑠$s$ at the end if Pak Chanek does all the steps optimally.