CF1610I Mashtali vs AtCoder

在多次尝试未果后，Mashtali 决定抄袭并修改 [一道 AtCoder 题目](https://atcoder.jp/contests/agc017/tasks/agc017_d)。于是有了如下的新题目： 有一棵包含 $n$ 个顶点的树，其中有一些非空的顶点集合被“钉”在地面上。 两名玩家在树上轮流进行如下操作： - 从树上删除一条边，然后移除所有不包含被钉顶点的连通块。无法进行操作（即所有边都已被删除）的玩家判负。 你将获得这棵树，但不会给出被钉顶点的集合。你的任务是，对于每个 $k$，判断如果只有顶点 $1, 2, 3, \ldots, k$ 被钉住，且双方都采取最优策略，谁会获胜。

输入的第一行包含一个整数 $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$ 条边连接的两个顶点。保证这些边构成一棵树。

输出一个长度为 $n$ 的字符串。第 $i$ 个字符为 '1' 表示在第 $i$ 种情况下先手必胜，为 '2' 表示后手必胜。

下图展示了第一个样例中的树：  如果 $k = 1$，那么先手可以切断边 $(1, 2)$。 如果 $k = 2$ 或 $k = 3$，先手可以切断边 $(2, 4)$，此后只剩下边 $(1, 2)$ 和 $(2, 3)$。在后手操作后，先手还能切断最后一条边。因此先手获胜。 由 ChatGPT 4.1 翻译