Mashtali vs AtCoder

题意翻译

有一棵含 $n$ 个结点的树，树上有若干结点被固定在地上。 蓝和橙想在树上玩个游戏，她们会轮流进行以下操作： - 从树上删除一条边，接着移除所有不包含固定在地上的结点的连通块。不能操作者输（不能操作即所有边均被删除）。 现在，蓝告诉了你她们进行游戏的树，但是没有告诉你被固定在地上的结点。她希望你对于所有 $k$，求出若结点 $1$ 到 $k$ 被固定在地上，先手还是后手有必胜策略。 输入的第一行包含一个数 $n$ 代表树的大小，接下来 $n-1$ 行每行含两数 $u_i,v_i$ 代表结点 $u_i$ 与结点 $v_i$ 间有一条边。 你需要输出一个长度为 $n$ 的字符串，第 $i$ 位若为 `1` 则代表当 $k=i$ 时先手必胜，为 `2` 则为后手必胜。 本题数据满足：$1 \leq 3\times10^5，1 \leq u_i,v_i \leq n，u_i \neq v_i$。

题目描述

After many unsuccessful tries, Mashtali decided to copy modify [an AtCoder problem](https://atcoder.jp/contests/agc017/tasks/agc017_d). 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.

输入输出格式

输入格式

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.

输出格式

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.

输入输出样例

输入样例 #1

5
1 2
2 3
2 4
4 5

输出样例 #1

11122

输入样例 #2

5
1 2
2 3
1 4
4 5

输出样例 #2

21122

输入样例 #3

6
1 2
2 4
5 1
6 3
3 2

输出样例 #3

111111

输入样例 #4

7
1 2
3 7
4 6
2 3
2 4
1 5

输出样例 #4

2212222

说明

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.