P16464 [UOI 2026] Game on a Tree

给定一棵有 $n$ 个顶点的树。每个叶子（即度为 $1$ 的顶点）都有一个状态：**活跃**或**不活跃**。初始时，所有叶子均为不活跃。 共有 $q$ 个询问，分为两种类型： - **1 v** —— 将叶子 $v$ 的状态切换为相反状态（活跃 $\leftrightarrow$ 不活跃）。保证 $v$ 是叶子（度为 $1$ 的顶点）。 - **2 s** —— 若令牌初始放置在顶点 $s$，判断下面所述游戏的胜者。保证 $s$ **不是**叶子（度 $\ge 2$ 的顶点）。 **游戏规则：** 有一枚令牌初始位于顶点 $s$。两名玩家轮流行动，先手先走。每次移动时，玩家将令牌移到一个未访问过的相邻顶点。当令牌位于一个无法再移动的顶点时游戏结束（即所有相邻顶点均已被访问过——该顶点必然是树的一个叶子）。若令牌最终停在一个**活跃**顶点，则后手获胜；否则，先手获胜。 ### 强制在线模式 若输入参数 $m = 1$，则每个询问中的实际顶点编号将被替换为加密后的编号。 考虑一个两种类型之一的询问： - `1 x` —— 一个加密的切换叶子状态的询问； - `2 x` —— 一个加密的从某个起始顶点开始的游戏询问。 令 $\mathit{acc}$ 为一个计数器，初始为 $0$。对于每个询问，数字 $x$ 通过以下公式解密为实际顶点编号 $v$： $$ v = ((x - 1 + \mathit{acc}) \bmod n) + 1. $$ 即： - 在询问 `1 x` 中，你需要切换叶子 $v$ 的状态； - 在询问 `2 x` 中，游戏从顶点 $v$ 开始。 每次询问后，计数器会更新： - 在解密后叶子为 $v$ 的 `1 x` 询问后：$\mathit{acc} = (\mathit{acc} + v) \bmod n$； - 在答案为 $w \in \{1, 2\}$ 的 `2 x` 询问后：$\mathit{acc} = (\mathit{acc} + w) \bmod n$。 若 $m = 0$，则询问不加密。此时，在询问 `1 v` 中，数字 $v$ 即为需要切换状态的叶子；在询问 `2 v` 中，数字 $v$ 即为游戏的起始顶点。

第一行包含三个整数 $n$、$q$ 和 $m$（$3 \le n \le 5 \cdot 10^5$，$1 \le q \le 5 \cdot 10^5$，$m \in \{0, 1\}$）。 接下来的 $n - 1$ 行描述树的边：每行两个整数 $u_i$ 和 $v_i$（$1 \le u_i, v_i \le n$，$u_i \ne v_i$）。 再接下来的 $q$ 行描述询问：每行一个类型 $t \in \{1, 2\}$ 和参数 $x$（$1 \le x \le n$）。若 $m = 1$，则 $x$ 是加密后的值。

对于每个第二类询问，在单独一行中输出一个数字：若先手获胜输出 $1$，若后手获胜输出 $2$。

在第一个例子中，树是一个以顶点 $1$ 为中心、叶子为 $2, 3, 4$ 的星形。初始时所有叶子均为不活跃：对于询问 `2 1`，先手可以唯一地走到任意一个叶子，令牌停在一个不活跃的叶子上——先手获胜，因此答案为 $1$。在三个激活所有叶子的类型 $1$ 询问之后，对于再次询问 `2 1`，无论先手走到哪里，令牌最终都会停在一个活跃的叶子上——后手获胜，因此答案为 $2$。 在第二个例子中，树呈 $Y$ 形：顶点 $3$ 连接顶点 $4$、$5$ 以及顶点 $1$，而顶点 $1$ 上连着叶子 $2$。询问 `2 3` 表示树以顶点 $3$ 为根。在激活任何叶子之前，先手可以从顶点 $3$ 在一步内到达一个不活跃的叶子（例如 $5$）——答案为 $1$。激活叶子 $2$、$4$ 和 $5$ 后，从 $3$ 出发的所有三条可能路径都以活跃叶子结束，因此先手无法避免失败——答案为 $2$。 第三个例子展示了在线模式（$m = 1$）在与第一个例子相同的树上的运行。初始 $\mathit{acc} = 0$，因此第一个加密询问 `2 1` 被解密为 `2 1` 并得到答案 $1$，之后 $\mathit{acc} = 1$。下一个加密询问 `1 1` 解密为 `1 2`（因为 $((1 - 1 + 1) \bmod 4) + 1 = 2$），激活叶子 $2$，然后 $\mathit{acc} = (1 + 2) \bmod 4 = 3$。类似地，`1 4` 解密为 `1 3`（激活叶子 $3$，$\mathit{acc} = 2$），`1 2` 解密为 `1 4`（激活叶子 $4$，$\mathit{acc} = 2$）。最后一个加密询问 `2 3` 解密为 `2 1` 并返回 $2$。 ### 计分 - （$4$ 分）：$n, q \le 1000$，$m = 0$； - （$8$ 分）：叶子永远不会从活跃变回不活跃，$s = 1$，$m = 0$； - （$13$ 分）：叶子永远不会从活跃变回不活跃，每个询问中令牌初始都在顶点 $1$，$m = 1$； - （$21$ 分）：$m = 0$，存在整数 $k \ge 1$ 使得 $n = 2^k - 1$，且树边对于所有 $2 \le i \le n$ 形式为 $(i, \lfloor i / 2 \rfloor)$。 - （$8$ 分）：仅顶点 $1$ 的度数大于 $2$，$m = 0$； - （$19$ 分）：$s = 1$，$m = 0$； - （$19$ 分）：$n \le 10^5$，$m = 0$； - （$8$ 分）：无额外限制。 翻译由 DeepSeek V4 Pro 完成