P16464 [UOI 2026] Game on a Tree

You are given a tree with $n$ vertices. Each leaf (that is, a vertex of degree $1$) has a status: $\textbf{active}$ or $\textbf{inactive}$. Initially, all leaves are inactive. There are $q$ queries of two types: - $\textbf{1 v}$ --- change the status of leaf $v$ to the opposite one (active $\leftrightarrow$ inactive). It is guaranteed that $v$ is a leaf (a vertex of degree $1$). - $\textbf{2 s}$ --- determine who wins the game described below, if the token is initially placed at vertex $s$. It is guaranteed that $s$ is $\textbf{not}$ a leaf (a vertex of degree $\ge 2$). $\textbf{Game:}$ there is a token initially placed at vertex $s$. Two players take turns, with the first player moving first. On each move, a player moves the token to an unvisited adjacent vertex. The game ends when the token is at a vertex from which it cannot move anywhere (that is, all adjacent vertices have already been visited --- this is necessarily a leaf of the graph). The second player wins if the token ends its move at an $\textbf{active}$ vertex; otherwise, the first player wins. ### Online mode If the input parameter $m = 1$, then in each query the actual vertex number is replaced by an encrypted number. Consider a query of one of the two types: - $\texttt{1 x}$ --- an encrypted query to change the status of a leaf; - $\texttt{2 x}$ --- an encrypted query for a game from some starting vertex. Let $\mathit{acc}$ be a counter, initially equal to $0$. For each query, the number $x$ is decrypted into the actual vertex number $v$ by the formula $$ v = ((x - 1 + \mathit{acc}) \bmod n) + 1. $$ That is: - in query $\texttt{1 x}$, you need to change the status of leaf $v$; - in query $\texttt{2 x}$, the game starts at vertex $v$. After each query, the counter is updated: - after query $\texttt{1 x}$ with decrypted leaf $v$: $\mathit{acc} = (\mathit{acc} + v) \bmod n$; - after query $\texttt{2 x}$ with answer $w \in \{1, 2\}$: $\mathit{acc} = (\mathit{acc} + w) \bmod n$. If $m = 0$, then the queries are not encrypted. In that case, in query $\texttt{1 v}$ the number $v$ is the leaf whose status must be changed, and in query $\texttt{2 v}$ the number $v$ is the starting vertex of the game.

The first line contains three integers $n$, $q$, and $m$ ($3 \le n \le 5 \cdot 10^5$, $1 \le q \le 5 \cdot 10^5$, $m \in \{0, 1\}$). The next $n - 1$ lines contain the edges of the tree: two integers $u_i$ and $v_i$ each ($1 \le u_i, v_i \le n$, $u_i \ne v_i$). The next $q$ lines contain the queries: type $t \in \{1, 2\}$ and argument $x$ ($1 \le x \le n$). If $m = 1$, then $x$ is an encrypted value.

For each query of the second type, output one number in a separate line: $1$ if the first player wins, or $2$ if the second player wins.

In the first example, the tree is a star with vertex $1$ in the center and leaves $2, 3, 4$. Initially all leaves are inactive: for query $\texttt{2 1}$, the first player makes the only move to any leaf, and the token stops at an inactive leaf --- the first player wins, so the answer is $1$. After three queries of type $\texttt{1}$ that activate all leaves, for the repeated query $\texttt{2 1}$, no matter where the first player moves, the token ends at an active leaf --- the second player wins, so the answer is $2$. In the second example, the tree has a $\textit{Y}$ shape: vertex $3$ is connected to vertices $4$, $5$, and to vertex $1$, which has leaf $2$ attached to it. Query $\texttt{2 3}$ means that the tree is rooted at vertex $3$. Before activating any leaves, the first player can reach an inactive leaf from vertex $3$ in one move (for example, to $5$) --- answer $1$. After activating leaves $2$, $4$, and $5$, all three possible paths from $3$ end at an active leaf, so the first player cannot avoid losing --- answer $2$. The third example demonstrates the online mode ($m = 1$) on the same tree as in the first example. The initial value is $\mathit{acc} = 0$, so the first encrypted query $\texttt{2 1}$ is decoded as $\texttt{2 1}$ and gives answer $1$, after which $\mathit{acc} = 1$. The next encrypted query $\texttt{1 1}$ is decoded as $\texttt{1 2}$ (because $((1 - 1 + 1) \bmod 4) + 1 = 2$), activating leaf $2$, and then $\mathit{acc} = (1 + 2) \bmod 4 = 3$. Similarly, $\texttt{1 4}$ is decoded as $\texttt{1 3}$ (activating leaf $3$, $\mathit{acc} = 2$), and $\texttt{1 2}$ --- as $\texttt{1 4}$ (activating leaf $4$, $\mathit{acc} = 2$). The last encrypted query $\texttt{2 3}$ is decoded as $\texttt{2 1}$ and returns $2$. ### Scoring - ($4$ points): $n, q \le 1000$, $m = 0$; - ($8$ points): a leaf never changes its status from active to inactive, $s = 1$, $m = 0$; - ($13$ points): a leaf never changes its status from active to inactive, the token is initially at vertex $1$ in every query, $m = 1$; - ($21$ points): $m = 0$, there exists an integer $k \ge 1$ such that $n = 2^k - 1$, and the tree edges are of the form $(i, \lfloor i / 2 \rfloor)$ for all $2 \le i \le n$. - ($8$ points): only vertex $1$ has degree greater than $2$, $m = 0$; - ($19$ points): $s = 1$, $m = 0$; - ($19$ points): $n \le 10^5$, $m = 0$; - ($8$ points): no additional constraints.