CF2230F Game on Growing Tree

考虑一个双人游戏：Alice 和 Bob。他们有一棵树 $T$；初始时，树上的每个顶点都是白色的。Alice 和 Bob 轮流进行操作：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$ 次操作后的树上进行游戏的得分。

由 DeepSeek-V4 翻译