Mashtali vs AtCoder (Codeforces 1610I)
Tags: Others, games

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

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.

Sample Inputs:
5
1 2
2 3
2 4
4 5

5
1 2
2 3
1 4
4 5

6
1 2
2 4
5 1
6 3
3 2

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

Sample Outputs:
11122

21122

111111

2212222

Solution (Python):
import sys
input = sys.stdin.buffer.readline
N = int(input())
T = [[] for i in range(N)]
for i in range(1, N):
    (u, v) = map(int, input().split())
    u -= 1
    v -= 1
    T[u].append(v)
    T[v].append(u)
stk = [(1, 0)]
par = [-1] * N
dp = [0] * N
while stk:
    (t, u) = stk.pop()
    if t == 1:
        stk.append((2, u))
        for v in T[u]:
            if v == par[u]:
                continue
            par[v] = u
            stk.append((1, v))
    else:
        for v in T[u]:
            if v == par[u]:
                continue
            dp[u] ^= dp[v] + 1
vis = [False] * N
vis[0] = True
ans = dp[0]
res = []
for i in range(N):
    u = i
    while not vis[u]:
        ans ^= dp[u] + 1 ^ dp[u] ^ 1
        vis[u] = True
        u = par[u]
    res.append('2' if ans == 0 else '1')
print('%s' % ''.join(res))

Solution (Python):
import sys
input = sys.stdin.buffer.readline

def iter_dfs(adj):
    (parent, grundy) = [[0] * len(adj) for _ in range(2)]
    parent[0] = -1
    stk = [(1, 0)]
    while stk:
        (step, u) = stk.pop()
        if step == 1:
            stk.append((2, u))
            for v in adj[u]:
                if v == parent[u]:
                    continue
                parent[v] = u
                stk.append((1, v))
        elif step == 2:
            for v in adj[u]:
                if v == parent[u]:
                    continue
                grundy[u] ^= grundy[v] + 1
    return (parent, grundy)

def solution():
    n = int(input())
    adj = [[] for _ in range(n)]
    for _ in range(n - 1):
        (u, v) = list(map(int, input().strip().split()))
        adj[u - 1].append(v - 1)
        adj[v - 1].append(u - 1)
    (parent, grundy) = iter_dfs(adj)
    lookup = [0] * n
    lookup[0] = 1
    curr = grundy[0]
    result = []
    for u in range(n):
        while not lookup[u]:
            lookup[u] = 1
            curr ^= grundy[u] + 1 ^ grundy[u] ^ 1
            u = parent[u]
        result.append('1' if curr else '2')
    return ''.join(result)
print('%s' % solution())

Solution (Python):
import sys
input = sys.stdin.buffer.readline

def iter_dfs(adj):
    (parent, grundy) = [[0] * len(adj) for _ in range(2)]
    parent[0] = -1
    stk = [(1, 0)]
    while stk:
        (step, u) = stk.pop()
        if step == 1:
            stk.append((2, u))
            for v in adj[u]:
                if v == parent[u]:
                    continue
                parent[v] = u
                stk.append((1, v))
        elif step == 2:
            for v in adj[u]:
                if v == parent[u]:
                    continue
                grundy[u] ^= grundy[v] + 1
    return (parent, grundy)

def solution():
    n = int(input())
    adj = [[] for _ in range(n)]
    for _ in range(n - 1):
        (u, v) = list(map(int, input().strip().split()))
        adj[u - 1].append(v - 1)
        adj[v - 1].append(u - 1)
    (parent, grundy) = iter_dfs(adj)
    lookup = [0] * n
    lookup[0] = 1
    curr = grundy[0]
    result = []
    for u in range(n):
        while not lookup[u]:
            lookup[u] = 1
            curr ^= grundy[u] + 1 ^ grundy[u] ^ 1
            u = parent[u]
        result.append('1' if curr else '2')
    return ''.join(result)
print('%s' % solution())