← 返回题目列表

AtCoder · arc164_f

F. 子树黑白棋

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

分数: 900 点

问题陈述

你得到了一棵有根的树 N 顶点编号自 1 to N,植根于顶点 1。顶点的父级 i 是顶点 p_i (2\leq i\leq N).

Alice 和 Bob 使用这棵树玩一个游戏,如下所示。

  • Alice 首先,Bob 第二。他们轮流将一块石头(一面为白色,一面为黑色)放置在树的顶点上。爱丽丝将石头的白色面朝上放置,鲍勃将石头的黑色面朝上放置。
  • 在每一回合中,石头只能放置在本身没有石头的顶点上,而其所有后代上都已经有石头了。
  • 当在顶点上放置棋子时,该顶点后代上的所有棋子都会翻转(放置的棋子本身不会翻转)。

当所有顶点都有棋子时游戏结束。爱丽丝的分数就是此时白面朝上的棋子数量。

Alice 尝试最大化她的分数,而 Bob 尝试最小化 Alice 的分数。如果两者都发挥最佳,爱丽丝的得分是多少?

约束

  • 2 \leq N \leq 2 \times 10^5
  • 1 \leq p_i < i (2\leq i \leq N)
  • 所有输入值均为整数。
  • 给定的图是一棵树。

输入

输入由标准输入按以下格式给出:

N
p_2 p_3 \ldots p_N

输出

将答案打印为整数。


示例输入 1

4
1 1 2

示例输出 1

2

在给定的树中,最初可以放置石头的唯一顶点是 3 和 4。从这里开始的一种可能的进展如下。

  • 爱丽丝在顶点放置了一块石头,白色的一面朝上 4。执行此操作后,顶点的所有后代 2 有石头,所以现在可以在顶点上放置石头 2.
  • 鲍勃放置了一块石头,黑色面朝上在顶点 2 并翻转顶点上的石头 4 将黑色面朝上。
  • 爱丽丝在顶点放置了一块石头,白色的一面朝上 3.
  • 鲍勃放置了一块石头,黑色面朝上在顶点 1 并翻转顶点上的所有石头 2, 3,和 4.

在这种情况下,游戏结束时,顶点上的棋子 1, 2, 3,和 4 分别为黑色、白色、黑色和白色面朝上。事实上,这个进程是两个玩家的最佳移动顺序的一个例子;答案是 2.


示例输入 2

7
1 1 2 4 4 4

示例输出 2

5