F. 生长树上的游戏 / Game on Growing Tree

题目描述

考虑一个两人游戏：Alice 和 Bob。他们有一棵树 $T$，初始所有顶点为 白色。两人轮流行动：Alice 先手，然后 Bob，然后 Alice，以此类推。

Alice 的第一回合必须选择一个顶点放上棋子，并将其涂成 红色。之后每回合（除第一回合外），Alice 必须将棋子移动到相邻的一个 白色 顶点并将其涂成 红色。如果 Alice 回合开始时，棋子所在顶点没有相邻白色顶点，游戏结束。

Bob 的每回合必须选择一个白色顶点涂成 蓝色。如果 Bob 回合开始时树中没有白色顶点，游戏结束。

游戏最终得分为 红色 顶点数。Alice 想最大化得分，Bob 想最小化得分。双方均采取最优策略。

以上是游戏描述。以下是题目。

给定一棵初始只有顶点 $1$ 的树。然后依次执行 $q$ 次操作：第 $i$ 次操作添加一个新顶点（编号 $i+1$），并与顶点 $v_i$ 连边。每次操作后，你需要在当前树上回答 Alice 和 Bob 游戏的最优得分。

输入格式

第一行包含一个整数 $q$ ($1 \le q \le 2 \cdot 10^5$) — 操作次数。

第二行包含 $q$ 个整数 $v_1, v_2, \dots, v_q$ ($1 \le v_i \le i$)，其中 $v_i$ 是第 $i$ 次操作中新顶点 $(i+1)$ 连接的顶点编号。

输出格式

输出 $q$ 个整数，第 $i$ 个数表示执行完前 $i$ 次操作后的最优游戏得分。

样例

2
3
1 1 1
4
1 1 1 1

2
2