分数: 500 点
问题陈述
高桥和青木将使用有根树玩一个游戏 n 顶点,编号 1 通过 n。 树的根是顶点 1。对于每个 v=2,\dots,n,Vertex 的父级 v is p_v。 最初,每个顶点上有一枚硬币。 1.
高桥和青木将交替进行以下操作,高桥先行:
- 如果该棋子占据的顶点上有一枚硬币:拿到硬币并结束他的回合。
- 如果棋子占据的顶点上没有硬币:按如下方式移动棋子(或结束游戏)。
- 如果该棋子占据的顶点的子节点中有上面有硬币的顶点,则选择一个这样的顶点,将棋子移动到该顶点,并结束他的回合。
- 否则,如果棋子在根上,则结束游戏;如果不是,则将该棋子移动到该棋子所占据的顶点的父级并结束他的回合。
高桥和青木都会以最佳方式发挥作用,以最大化他们获得的金币数量。求高桥将获得的硬币数量。
约束
- 2\le n \le 10^5
- 1\le p_v \lt v
输入
输入由标准输入按以下格式给出:
n p_2 \dots p_n
输出
打印当两个玩家发挥最佳状态时高桥将获得的硬币数量。
示例输入 1
10 1 2 3 4 5 6 7 8 9
示例输出 1
10
玩家别无选择,游戏将始终如下进行,因此高桥将获得所有硬币。
- 高桥在 Vertex 上获得硬币 1.
- 青木将棋子移动到顶点 2.
- 高桥在 Vertex 上获得硬币 2.
- 青木将棋子移动到顶点 3.
- \vdots
- 高桥在 Vertex 上获得硬币 10.
- 青木将棋子移动到顶点 9.
- 高桥将棋子移动到顶点 8.
- 青木将棋子移动到顶点 7.
- \vdots
- 高桥将棋子移动到顶点 2.
- 青木将棋子移动到顶点 1.
- 游戏结束。
示例输入 2
5 1 2 3 1
示例输出 2
2
首先,高桥在 Vertex 上获得硬币 1。 然后,青木可以将棋子移动到顶点 2 或顶点 5。 如果他把它移到顶点 2,Aoki 最终将在 Vertex 上获得硬币 5。 另一方面,如果他将其移动到顶点 5,Aoki最终会在Vertex上获得金币 2, 3,和 4。 由于 Aoki 会以最佳方式发挥最大的金币数量,因此他会选择将棋子移至 Vertex 5。 这样,高桥就会得到两枚硬币。
示例输入 3
10 1 1 3 1 3 6 7 6 6
示例输出 3
5