Hanging Hearts (Codeforces 1740E)
Tags: 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):  Choose a card $$$x$$$ such that no other cards are hanging onto it.  Append the number written on card $$$x$$$ to the end of $$$s$$$.  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$$$.  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: 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: 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.

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:  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]$$$.  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]$$$.  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]$$$.  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]$$$.  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]$$$.  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.

Sample Inputs:
6
1 2 1 4 2

2
1

Sample Outputs:
4

2

Solution (Python):
n = int(input())
p = [-1] + [x - 1 for x in list(map(int, input().split()))]
(h, dp) = ([1] * n, [0] * n)
for i in range(n - 1, -1, -1):
    dp[i] = max(dp[i], h[i])
    if i:
        dp[p[i]] += dp[i]
        h[p[i]] = max(h[p[i]], h[i] + 1)
print(dp[0])

Solution (Python):
n = int(input())
p = [-1] + [x - 1 for x in list(map(int, input().split()))]
(h, dp) = ([1] * n, [0] * n)
for i in range(n - 1, -1, -1):
    dp[i] = max(dp[i], h[i])
    if i:
        dp[p[i]] += dp[i]
        h[p[i]] = max(h[p[i]], h[i] + 1)
print(dp[0])

Solution (Python):
n = int(input())
a = [-1] + [int(o) - 1 for o in input().split()]
f = [0] * n
dp = [0] * n
for i in range(n - 1, 0, -1):
    f[a[i]] = max(f[i] + 1, f[a[i]])
for i in range(n - 1, 0, -1):
    dp[i] = max(dp[i], f[i] + 1)
    dp[a[i]] += dp[i]
print(max(dp[0], f[0] + 1))