你被给予 有根树 具有 $$$n$$$ 节点,编号从 $$$1$$$ 到 $$$n$$$,根于节点 $$$1$$$。对于每个节点 $$$i$$$ ($$$2 \le i \le n$$$),其父节点是节点 $$$p_i$$$。对于每个节点 $$$i$$$,如果它是 叶 (没有子节点的节点),上面写有整数$$$i$$$。否则什么也不会写。
节点 $$$u$$$ 是 后代 节点 $$$v$$$ 的 如果 $$$u = v$$$,或者 $$$u$$$ 不是根并且 $$$u$$$ 的父级是 $$$v$$$ 的后代。
现在,您和您的朋友在这棵树上轮流玩游戏:您先移动,然后是您的朋友,依此类推。每回合,当前玩家必须选择一个节点 $$$v$$$,然后删除 $$$v$$$ 的整个子树(即 $$$v$$$ 的所有后代,包括 $$$v$$$ 本身)。仅在以下情况下才允许移动: 之后 删除后,至少一个写有整数的节点仍保留在树中。
当无法进行进一步的移动时,游戏结束。此时,只剩下一个写有整数的节点;的 分数 本实验的 是该节点上的整数。
您的目标是最小化分数,而您的朋友的目标是最大化分数。假设您和您的朋友发挥最佳,确定游戏的得分。
输入
输入的第一行包含一个整数 $$$n$$$ ($$$2 \le n \le 500\,000$$$)。
第二行包含 $$$n-1$$$ 整数 $$$p_2, p_3, \ldots, p_n$$$ ($$$1 \le p_i \lt i$$$ 对于所有 $$$2 \le i \le n$$$)。
输出
假设您和您的朋友发挥最佳,输出游戏得分。
示例
输入复制
7 1 2 2 1 5 5
输出复制
4
输入复制
9 1 1 3 2 5 4 5 5
输出复制
7
注意
示例输入/输出 #1 的说明
给定的树如图 B.1 (a) 所示。
![]() |
| 图 B.1:示例输入 #1 的图示。 |
两名玩家唯一的最佳动作如下:
- 您选择节点 $$$5$$$。然后节点 $$$5$$$、$$$6$$$ 和 $$$7$$$ 被删除(图 B.1(b))。
- 你的朋友选择节点$$$3$$$。然后仅删除节点 $$$3$$$(图 B.1(c))。
- 你不能进行任何动作,游戏结束。
示例输入/输出#2 的说明
给定的树如图 B.2 所示。对您来说,最佳的移动方式之一是选择节点 $$$2$$$。之后游戏结束,得分为$$$7$$$。
![]() |
| 图 B.2:示例输入 #2 的图示。 |

