CF1610I.Mashtali vs AtCoder

After many unsuccessful tries, Mashtali decided to copy modify an AtCoder problem. So here is his copied new problem:

There is a tree with $n$ vertices and some non-empty set of the vertices are pinned to the ground.

Two players play a game against each other on the tree. They alternately perform the following action:

• Remove an edge from the tree, then remove every connected component that has no pinned vertex.

  The player who cannot move loses(every edge has been deleted already).

You are given the tree, but not the set of the pinned vertices. Your task is to determine, for each $k$, the winner of the game, if only the vertices $1, 2, 3, \ldots, k$ are pinned and both players play optimally.

经过多次失败的尝试后，Mashtali 决定复制并修改一道 AtCoder 题目。于是他得到了如下这道新题目：

给定一棵含 $n$ 个顶点的树，其中某些非空顶点子集被固定在地面上（即“被钉住”）。

两名玩家在该树上进行博弈，轮流执行以下操作：

• 从树中删除一条边，然后删去所有不包含任何被钉住顶点的连通分量。

无法进行操作的玩家判负（即所有边均已被删除）。

你将获得这棵树，但不知道哪些顶点被钉住。你的任务是：对每个 $k$，判断当且仅当顶点 $1, 2, 3, \ldots, k$ 被钉住时，在双方均采取最优策略的前提下，游戏的获胜方是谁。

The first line of input contains an integer $n$ — the number of vertices ($1 \le n \le 3 \cdot 10^5$).

The $i$-th of the following $n-1$ lines contains two integers $u_i, v_i$ ($1 \le u_i, v_i \le n$, $u_i \ne v_i$) — the endpoints of the $i$-th edge. It's guaranteed that these edges form a tree.

输入的第一行包含一个整数 $n$ —— 顶点的数量（$1 \le n \le 3 \cdot 10^5$）。

接下来的 $n-1$ 行中，第 $i$ 行包含两个整数 $u_i, v_i$（$1 \le u_i, v_i \le n$，且 $u_i \ne v_i$）—— 表示第 $i$ 条边的两个端点。保证这些边构成一棵树。

Print a string of length $n$. The $i$-th character should be '1' if the first player wins the $i$-th scenario, and '2' otherwise.

输出一个长度为 $n$ 的字符串。其中第 $i$ 个字符应为 '1'，如果先手玩家在第 $i$ 个场景中获胜；否则为 '2'。

Below you can see the tree in the first sample :

If $k = 1$ then the first player can cut the edge $(1, 2)$.

If $k = 2$ or $k = 3$, the first player can cut the edge $(2, 4)$, after that only the edges $(1, 2)$ and $(2, 3)$ remain. After the second players move, there will be a single edge left for the first player to cut. So first player wins.

下面你可以看到第一个样例中的树：

若 $k = 1$，则先手玩家可以切断边 $(1, 2)$。

若 $k = 2$ 或 $k = 3$，先手玩家可以切断边 $(2, 4)$，此后仅剩边 $(1, 2)$ 和 $(2, 3)$。在后手玩家行动之后，将恰好剩余一条边供先手玩家切断。因此先手玩家获胜。