← 返回题目列表

AtCoder · arc112_c

C. DFS 游戏

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

分数: 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