Hanging Hearts
Contest: Codeforces Round 831 (Div. 1 + Div. 2)
Difficulty rating: 1800
Tags: constructive algorithms, data structures, dfs and similar, dp, greedy, trees

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 > 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, \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]$$$.

Input format:
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 < i$$$) describing which card that each card hangs onto.

Output format:
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.

Constraints:
Time limit: 1.0 s
Memory limit: 256.0 MB

Note:
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 > 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 > 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.

Example input:
6
1 2 1 4 2

Example output:
4

Example input:
2
1

Example output:
2

Editorial:
The cards form a rooted tree with card $$$i$$$ being the root, where for each $$$i$$$ ($$$i>1$$$), the parent of card $$$i$$$ is $$$p_i$$$.
Let $$$w_i$$$ be the number on card $$$i$$$ when it is about to get removed. To remove card $$$i$$$, we must previously remove all cards in the subtree of $$$i$$$ other than $$$i$$$ itself. Thus, we can see that $$$w_i$$$ is the minimum value of $$$a$$$ out of all cards in the subtree of $$$i$$$.
Let the sequence $$$[v_1,v_2,v_3,\ldots]$$$ mean that the $$$i$$$-th element of the longest non-decreasing subsequence comes from card $$$v_i$$$. Then, we can get the following observations:
• We can only remove card $$$i$$$ if all other cards in the subtree of $$$i$$$ have been removed. Hence, for each $$$v_i$$$, every $$$v_j$$$ with $$$j>i$$$ must not be in the subtree of $$$v_i$$$.
• We can make $$$v_{i+1}$$$ to be the ancestor of $$$v_i$$$ by making $$$w_{v_{i+1}}=w_{v_i}$$$. This can be done by making it such that the minimum value of $$$a$$$ in the subtree of $$$v_i$$$ is simultaneously the minimum value of $$$a$$$ in the subtree of $$$v_{i+1}$$$.
• If $$$v_{i+1}$$$ is not the ancestor of $$$v_i$$$, then $$$w_{v_{i+1}} \neq w_{v_i}$$$ must hold. Because $$$v$$$ forms a non-decreasing sequence, then $$$w_{v_{i+1}} > w_{v_i}$$$ must hold. That means, $$$w_{v_{i+1}}$$$ is guaranteed to be larger than the values of $$$w$$$ for all ancestors of $$$v_i$$$. This means, after $$$v_{i+1}$$$, $$$v$$$ cannot continue with any ancestors of $$$v_i$$$.
From the information above, it means that when constructing $$$v$$$, we do one the following operation several times:
• Append an ancestor of the last card.
• Append a card that is not an ancestor of the last card and not a descendant of any of the previous cards. After this, we cannot choose any ancestor of the card before this new card.
In the optimal configuration, the sequence $$$v$$$ resembles the following:
• It consists of several paths of cards where each path is from a card to one of its ancestors.
• For any pair of cards from two different paths, one must not be an ancestor of the other.
We will use dynamic programming on tree. Let $$$dp[i]$$$ denote the length of the longest non-decreasing subsequence created from only doing operations to the subtree of $$$i$$$. Then, we have two cases:
• If card $$$i$$$ is used in the longest non-decreasing subsequence, then the maximum answer is the maximum number of cards in a path from card $$$i$$$ to one of the cards in the subtree of $$$i$$$.
• If card $$$i$$$ is not used in the longest non-decreasing subsequence, then the maximum answer is the sum of $$$dp$$$ values of the children of card $$$i$$$.
Time complexity: $$$O(n)$$$