CF2230F.Game on Growing Tree

Consider a game for two players: Alice and Bob. They have a tree $T$; initially, every vertex of this tree is white. Alice and Bob take turns: Alice goes first, then Bob, then Alice again, then Bob again, and so on.

During Alice's first turn, she has to choose a vertex and put a chip in it, then paint the chosen vertex red. During every turn except for the first one, Alice has to move the chip into an adjacent white vertex and paint that vertex red. If, at the start of Alice's turn, there are no white vertices adjacent to the vertex with the chip, the game ends.

During each of Bob's turns, he has to choose a white vertex and paint it blue. If there are no white vertices in the tree at the start of Bob's turn, the game ends.

The final score of the game is the number of red vertices. Alice wants to maximize the score, Bob wants to minimize it. Both players play optimally.

This is the description of the game. The statement of the problem follows.

You are given a tree, initially consisting of only one vertex numbered $1$. Then, $q$ queries are performed; during the $i$-th query, a new vertex is added to the tree; this new vertex gets the number $(i+1)$ and is connected to the vertex $v_i$ by an edge. After each query, you have to print the final score of the game if Alice and Bob play on the current tree.

考虑一个双人游戏：爱丽丝（Alice）和鲍勃（Bob）。他们拥有一棵树 $T$；初始时，该树的每个顶点均为白色。爱丽丝与鲍勃轮流进行操作：爱丽丝先手，随后鲍勃，接着爱丽丝，再鲍勃，依此类推。

在爱丽丝的第一回合中，她必须选择一个顶点，并在该顶点上放置一枚棋子，然后将所选顶点涂成红色。在除第一回合外的每一回合中，爱丽丝必须将棋子移动至一个与当前棋子所在顶点相邻的白色顶点，并将该顶点涂成红色。若在爱丽丝回合开始时，棋子所在顶点周围不存在任何白色顶点，则游戏结束。

在鲍勃的每一回合中，他必须选择一个白色顶点并将其涂成蓝色。若在鲍勃回合开始时，树中已无白色顶点，则游戏结束。

游戏的最终得分为红色顶点的数量。爱丽丝希望最大化该得分，而鲍勃希望最小化该得分。双方均以最优策略进行游戏。

以上即为该游戏的规则描述。问题陈述如下：

给定一棵初始仅含一个编号为 $1$ 的顶点的树。随后执行 $q$ 次查询；在第 $i$ 次查询中，向树中添加一个新顶点；该新顶点编号为 $(i+1)$，并通过一条边与顶点 $v_i$ 相连。每次查询后，你需要输出：若爱丽丝与鲍勃在当前树上进行上述游戏，其最终得分是多少。

The first line contains one integer $q$ ($1 \le q \le 2 \cdot 10^5$) — the number of queries.

The second line contains $q$ integers $v_1, v_2, \dots, v_q$ ($1 \le v_i \le i$), where $v_i$ is the vertex that gets connected with the vertex $(i+1)$ during the $i$-th query.

第一行包含一个整数 $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)$ 相连的顶点。

Print $q$ integers; the $i$-th of these integers should be the score if Alice and Bob play on the tree that you get after processing the $i$-th query.

输出 $q$ 个整数；其中第 $i$ 个整数应为 Alice 和 Bob 在处理完第 $i$ 个查询后所得树上进行游戏时的得分。

null