← 返回题目列表

Codeforces · 1740/E

E. 悬着的心

中文机器翻译题面 查看原题

Pak Chanek 有 $$$n$$$ 空白心形卡片。卡 $$$1$$$ 直接固定在墙上,而其他每张卡都通过一根绳子正好悬挂在另一张卡上。具体来说,卡 $$$i$$$ ($$$i > 1$$$) 挂在卡 $$$p_i$$$ ($$$p_i < i$$$) 上。

一开始,Pak Chanek 必须在每张卡片上写下一个整数。他通过选择 $$$[1, 2, \dots, n]$$$ 的任意排列 $$$a$$$ 来做到这一点。那么,写在卡片$$$i$$$上的数字是$$$a_i$$$。

之后,Pak Chanek 必须执行以下操作 $$$n$$$ 次,同时保持序列 $$$s$$$(最初为空):

1. 选择一张 $$$x$$$ 的牌,使其上没有其他牌。
2. 将卡片$$$x$$$ 上写的数字附加到$$$s$$$ 的末尾。
3. 如果 $$$x \neq 1$$$ 并且卡 $$$p_x$$$ 上的号码大于卡 $$$x$$$ 上的号码,则将卡 $$$p_x$$$ 上的号码替换为卡 $$$x$$$ 上的号码。
4. 取出卡$$$x$$$。

之后,Pak Chanek 将得到一个包含 $$$n$$$ 元素的序列 $$$s$$$。如果 Pak Chanek 最优地完成所有步骤,则 $$$s$$$ 的最长非递减子序列 $$$^\dagger$$$ 的最大长度是多少?

$$$^\dagger$$$ 序列 $$$b$$$ 是序列 $$$c$$$ 的子序列,如果 $$$b$$$ 可以通过删除几个(可能是零个或全部)元素从 $$$c$$$ 获得。例如,$$$[3,1]$$$ 是 $$$[3,2,1]$$$、$$$[4,3,1]$$$ 和 $$$[3,1]$$$ 的子序列,但不是 $$$[1,3,3,7]$$$ 和 $$$[3,10,4]$$$ 的子序列。

输入

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

第二行包含 $$$n - 1$$$ 整数 $$$p_2, p_3, \dots, p_n$$$ ($$$1 \le p_i < i$$$) 描述每张牌挂在哪张牌上。

输出

打印一个整数——如果 Pak Chanek 最优地完成了所有步骤,则 $$$s$$$ 的最长非递减子序列的最大长度在末尾。

示例

输入 #1

6
1 2 1 4 2

输出 #1

4

输入 #2

2
1

输出 #2

2

注意

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

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 > 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 > 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$$$。可以证明这确实是最大可能的长度。