← 返回题目列表

Codeforces · 2206/B

B. 子树删除游戏

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

你被给予 有根树 具有 $$$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))。
  • 你不能进行任何动作,游戏结束。
经过这些移动,只剩下一个写有整数的节点,即节点 $$$4$$$。这场比赛的得分是$$$4$$$。

示例输入/输出#2 的说明

给定的树如图 B.2 所示。对您来说,最佳的移动方式之一是选择节点 $$$2$$$。之后游戏结束,得分为$$$7$$$。

图 B.2:示例输入 #2 的图示。