AT_arc112_c.[ARC112C] DFS Game

高桥君和青木君用一棵有 $n$ 个顶点的有根树进行游戏。树的每个顶点编号为 $1$ 到 $n$。树的根为顶点 $1$，对于 $v=2,\dots,n$，顶点 $v$ 的父节点为 $p_v$。最开始，每个顶点上都有 $1$ 枚硬币，且顶点 $1$ 上放有棋子。

高桥君和青木君轮流进行如下操作，高桥君先手：

• 如果棋子所在的顶点上有硬币，则获得该硬币，结束本回合。
• 如果棋子所在的顶点上没有硬币，则按以下规则移动棋子（或结束游戏）：
  • 如果该顶点的子节点中存在有硬币的顶点，可以选择其中任意一个，将棋子移动到该顶点，结束本回合。
  • 如果不存在这样的子节点，且当前顶点是根节点，则游戏结束。否则，将棋子移动到当前顶点的父节点，结束本回合。

高桥君和青木君都会采取最优策略，使自己获得的硬币数量最大。请你求出高桥君最终能获得的硬币数量。

输入为以下格式，从标准输入读入。

$n$ $p_2$ $p_3$ $\dots$ $p_n$

输出在双方都采取最优策略时，高桥君能获得的硬币数量。

限制条件

• $2 \leq n \leq 10^5$
• $1 \leq p_v < v$

样例解释 1

由于双方都没有选择的余地，游戏必然按如下顺序进行，因此高桥君能获得所有硬币。

• 高桥君获得顶点 $1$ 上的硬币。
• 青木君将棋子移动到顶点 $2$。
• 高桥君获得顶点 $2$ 上的硬币。
• 青木君将棋子移动到顶点 $3$。
• $\vdots$
• 高桥君获得顶点 $10$ 上的硬币。
• 青木君将棋子移动到顶点 $9$。
• 高桥君将棋子移动到顶点 $8$。
• 青木君将棋子移动到顶点 $7$。
• $\vdots$
• 高桥君将棋子移动到顶点 $2$。
• 青木君将棋子移动到顶点 $1$。
• 游戏结束。

样例解释 2

首先，高桥君获得顶点 $1$ 上的硬币。之后，青木君可以选择将棋子移动到顶点 $2$ 或顶点 $5$。如果移动到顶点 $2$，青木君最终只能获得顶点 $5$ 上的硬币；如果移动到顶点 $5$，青木君最终能获得顶点 $2,3,4$ 上的硬币。由于青木君会采取最优策略，他会选择移动到顶点 $5$。因此，高桥君最终能获得 $2$ 枚硬币。

由 ChatGPT 4.1 翻译