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