CF2206B Subtree Removal Game

给定一棵有 $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 < i$，对所有 $2 \le i \le n$ 成立）。

输出在你和你的朋友都采取最优策略时，游戏的得分。

样例输入输出 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 的树结构和游戏过程。 由 ChatGPT 5 翻译