CF1740E.Hanging Hearts

Pak Chanek has $n$ blank heart-shaped cards. Card $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$ ($i \gt 1$) is hanging onto card $p_i$ ($p_i \lt 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, \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 $x \neq 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$^\dagger$ of $s$ at the end if Pak Chanek does all the steps optimally?

$^\dagger$ 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]$ is a subsequence of $[3,2,1]$, $[4,3,1]$ and $[3,1]$, but not $[1,3,3,7]$ and $[3,10,4]$.

帕克·查内克有 $n$ 张空白的心形卡片。第 $1$ 张卡片直接贴在墙上，其余每张卡片均通过一根细绳恰好悬挂在另一张卡片上。具体而言，第 $i$ 张卡片（$i > 1$）悬挂在第 $p_i$ 张卡片上（满足 $p_i < i$）。

最初，帕克·查内克必须在每张卡片上写一个整数。他通过选择 $[1, 2, \dots, n]$ 的任意一个排列 $a$ 来完成此操作；然后，第 $i$ 张卡片上所写的数字即为 $a_i$。

随后，帕克·查内克需执行以下操作共 $n$ 次，同时维护一个序列 $s$（初始为空）：

1. 选择一张卡片 $x$，使得没有其他卡片悬挂在它上面；
2. 将卡片 $x$ 上所写的数字添加到序列 $s$ 的末尾；
3. 若 $x \neq 1$ 且卡片 $p_x$ 上的数字大于卡片 $x$ 上的数字，则将卡片 $p_x$ 上的数字替换为卡片 $x$ 上的数字；
4. 移除卡片 $x$。

最终，帕克·查内克将得到一个长度为 $n$ 的序列 $s$。若帕克·查内克在整个过程中均采取最优策略，那么 $s$ 的最长非递减子序列$^\dagger$ 的最大可能长度是多少？

$^\dagger$ 序列 $b$ 是序列 $c$ 的一个子序列，当且仅当 $b$ 可通过从 $c$ 中删除若干（可能为零个或全部）元素而得到。例如，$[3,1]$ 是 $[3,2,1]$、$[4,3,1]$ 和 $[3,1]$ 的子序列，但不是 $[1,3,3,7]$ 和 $[3,10,4]$ 的子序列。

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

The second line contains $n - 1$ integers $p_2, p_3, \dots, p_n$ ($1 \le p_i \lt i$) describing which card that each card hangs onto.

第一行包含一个整数 $n$（$2 \le n \le 10^5$）—— 心形卡片的数量。

第二行包含 $n - 1$ 个整数 $p_2, p_3, \dots, p_n$（$1 \le p_i \lt i$），描述每张卡片所悬挂于的卡片编号。

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.

输出一个整数——如果 Pak Chanek 以最优方式执行所有步骤，字符串 $s$ 的最长非递减子序列的最大长度。

The following is the structure of the cards in the first example.

Pak Chanek can choose the permutation $a = [1, 5, 4, 3, 2, 6]$.

Let $w_i$ be the number written on card $i$. Initially, $w_i = a_i$. Pak Chanek can do the following operations in order:

1. Select card $5$. Append $w_5 = 2$ to the end of $s$. As $w_4 \gt w_5$, the value of $w_4$ becomes $2$. Remove card $5$. After this operation, $s = [2]$.
2. Select card $6$. Append $w_6 = 6$ to the end of $s$. As $w_2 \leq w_6$, the value of $w_2$ is left unchanged. Remove card $6$. After this operation, $s = [2, 6]$.
3. Select card $4$. Append $w_4 = 2$ to the end of $s$. As $w_1 \leq w_4$, the value of $w_1$ is left unchanged. Remove card $4$. After this operation, $s = [2, 6, 2]$.
4. Select card $3$. Append $w_3 = 4$ to the end of $s$. As $w_2 \gt w_3$, the value of $w_2$ becomes $4$. Remove card $3$. After this operation, $s = [2, 6, 2, 4]$.
5. Select card $2$. Append $w_2 = 4$ to the end of $s$. As $w_1 \leq w_2$, the value of $w_1$ is left unchanged. Remove card $2$. After this operation, $s = [2, 6, 2, 4, 4]$.
6. Select card $1$. Append $w_1 = 1$ to the end of $s$. Remove card $1$. After this operation, $s = [2, 6, 2, 4, 4, 1]$.

One of the longest non-decreasing subsequences of $s = [2, 6, 2, 4, 4, 1]$ is $[2, 2, 4, 4]$. Thus, the length of the longest non-decreasing subsequence of $s$ is $4$. It can be proven that this is indeed the maximum possible length.

以下是第一个示例中卡片的结构。

Pak Chanek 可以选择排列 $a = [1, 5, 4, 3, 2, 6]$。

令 $w_i$ 表示第 $i$ 张卡片上所写的数字。初始时，$w_i = a_i$。Pak Chanek 可按如下顺序执行以下操作：

1. 选择第 $5$ 张卡片。将 $w_5 = 2$ 追加到序列 $s$ 的末尾。由于 $w_4 \gt w_5$，$w_4$ 的值变为 $2$。移除第 $5$ 张卡片。该操作后，$s = [2]$。
2. 选择第 $6$ 张卡片。将 $w_6 = 6$ 追加到序列 $s$ 的末尾。由于 $w_2 \leq w_6$，$w_2$ 的值保持不变。移除第 $6$ 张卡片。该操作后，$s = [2, 6]$。
3. 选择第 $4$ 张卡片。将 $w_4 = 2$ 追加到序列 $s$ 的末尾。由于 $w_1 \leq w_4$，$w_1$ 的值保持不变。移除第 $4$ 张卡片。该操作后，$s = [2, 6, 2]$。
4. 选择第 $3$ 张卡片。将 $w_3 = 4$ 追加到序列 $s$ 的末尾。由于 $w_2 \gt w_3$，$w_2$ 的值变为 $4$。移除第 $3$ 张卡片。该操作后，$s = [2, 6, 2, 4]$。
5. 选择第 $2$ 张卡片。将 $w_2 = 4$ 追加到序列 $s$ 的末尾。由于 $w_1 \leq w_2$，$w_1$ 的值保持不变。移除第 $2$ 张卡片。该操作后，$s = [2, 6, 2, 4, 4]$。
6. 选择第 $1$ 张卡片。将 $w_1 = 1$ 追加到序列 $s$ 的末尾。移除第 $1$ 张卡片。该操作后，$s = [2, 6, 2, 4, 4, 1]$。

序列 $s = [2, 6, 2, 4, 4, 1]$ 的一个最长非递减子序列为 $[2, 2, 4, 4]$。因此，$s$ 的最长非递减子序列的长度为 $4$。可以证明，这确实是可能达到的最大长度。