AT_arc164_f.[ARC164F] Subtree Reversi

给定一棵有 $N$ 个顶点的有根树，顶点编号为 $1$ 到 $N$，以顶点 $1$ 为根。对于每个顶点 $i$（$2 \leq i \leq N$），其父节点为 $p_i$。

Alice 和 Bob 使用这棵树进行如下游戏：

• Alice 先手，Bob 后手，双方轮流在树的顶点上放置一枚石子。石子有正反两面，正面为白色，反面为黑色。Alice 总是将白色面朝上放置，Bob 总是将黑色面朝上放置。
• 每次只能在当前没有石子的顶点，并且其所有子孙顶点都已经放置了石子的顶点上放置石子。
• 放置石子时，需要将该顶点所有子孙上的石子全部翻面（但新放置的石子不翻面）。

当所有顶点都放置了石子后，游戏结束。此时，白色面朝上的石子数量即为 Alice 的得分。

Alice 希望最大化得分，Bob 希望最小化 Alice 的得分。双方都采取最优策略时，Alice 的得分是多少？

输入为一行，格式如下：

$N$ $p_2$ $p_3$ $\ldots$ $p_N$

输出一个整数，表示 Alice 的得分。

限制条件

• $2 \leq N \leq 2 \times 10^5$
• $1 \leq p_i < i$ （$2 \leq i \leq N$）
• 输入的所有值均为整数
• 给定的图结构保证是一棵树

样例解释 1

对于给定的树，最初可以放置石子的顶点只有 $3,4$。例如，游戏可以如下进行：

• Alice 在顶点 $4$ 放置白色面朝上的石子。此时，顶点 $2$ 的所有子孙都已放置石子，因此可以放置石子。
• Bob 在顶点 $2$ 放置黑色面朝上的石子，并将顶点 $4$ 的石子翻面，使其变为黑色面朝上。
• Alice 在顶点 $3$ 放置白色面朝上的石子。
• Bob 在顶点 $1$ 放置黑色面朝上的石子，并将顶点 $2,3,4$ 的石子全部翻面。

此时，顶点 $1,2,3,4$ 上的石子分别为黑、白、黑、白朝上。实际上，这是一种双方最优策略下的进行方式，答案为 $2$。

由 ChatGPT 4.1 翻译