Mashtali vs AtCoder
Contest: Codeforces Global Round 17
Difficulty rating: 3100
Tags: games, trees

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.

Input format:
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.

Output format:
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.

Constraints:
Time limit: 1.0 s
Memory limit: 256.0 MB

Note:
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.

Example input:
5
1 2
2 3
2 4
4 5

Example output:
11122

Example input:
5
1 2
2 3
1 4
4 5

Example output:
21122

Editorial:
First, please read the atcoder editorial for the $$$k=1$$$ case. Now, I just say how to calculate the grundy for greater $$$k$$$ and prove later:
Lets color all vertices that lie on the path between a pair of pinned vertices as black.(And others as white) Now, lets call an edge black if it connects two black vertices, And call an edge gray if it connects a black vertex to a white one. Now: $$$grundy = \text{xor of grundy of all gray edges xor parity of number of black edges}$$$. And that can be calculated when a new pinned vertex is added, move to the root and re-color all white edges as black.
complexity: $$$O(n)$$$
And the proof: We should prove that all lesser grundies are reachable and the grundy itself is not. The second one is easier. You either remove a white/gray edge, in which case the grundy changes because exactly one of the gray edges, changes its grundy. Otherwise, we remove a black edge, in which case you can show the parity of grundy changes(this one is easy to prove and left for the reader).
Now to prove all lesser grundies are achievable: First, If there was an even number of black edges, we can see our game as NIM on grundies of white edges. Also, If the lesser grundy we want is differs in the current grundy in not only the 0'th bit, Again we can choose one of the gray edges and perform our move in its subtree. So, we have odd number of black edges and we want to remove a black edge such that **even** number of black edges remain(note that some black edges may turn into white and gray ones.) And $$$\text{xor of grundy of gray edges in result tree = xor of grundies of gray edges in original tree}$$$. You can see that proving this suffice.
Imagine we have proved for $$$k=2$$$ case. For $$$3 \le k$$$ we use induction on $$$k$$$. If there was a pinned vertex with more than 1 black neighbour, We can cut the tree from that vertex(decompose edges to some components with this vertex appearing in all of them) and use induction on the independent components. Otherwise, the pinned vertices are leaves of the subtree of black vertices. (And we have at least $$$3$$$ leaves.)
lets decompose black edges to maximal paths such that the middle vertices of each path each have exactly $$$2$$$ black neighbours. (In other words, lets say we merge black vertices of degree $$$2$$$. now each merged edge is one of our paths.) Also note that by decomposing, we dont ignore the gray edge subtrees! For each gray edge we assign it to its black vertex from arbitrary path.(A black vertex could appear in more than one path.)
Since we have an odd number of black edges over-all, There is a path of odd length. Lets take a random odd path and call it special.(Let $$$u, v$$$ be its endpoints.)
Now, we solve the $$$k=2$$$ case on the $$$uv$$$ path. It removes a black edge and splits the tree into two components. Use induction on both trees. So, we can imagine vertices $$$u$$$ and $$$v$$$ are pinned after cutting the edge! And, while solving the $$$k=2$$$ case on $$$uv$$$ path, we had the same condition. This shows that if an edge on the $$$uv$$$ path has our condition only on this path, It also suffice for what we wanted to prove!
So, the only thing that remains to prove is the $$$k=2$$$ case.