AT_scpc2026_div1_i Tree, Game, and Query

Terra 和 Lulu 正在一棵包含 $N$ 个顶点和 $N-1$ 条边的树上玩棋盘游戏。树的每个顶点 $i$ 有一个权重 $V_i$ 和一个乘子 $W_i$。树中的第 $i$ 条边连接顶点 $u_i$ 和 $v_i$。初始时，所有乘子 $W_i$ 都为 $1$，顶点 $1$ 作为树根。 当游戏开始时，移除每个顶点 $i$ 上现有的所有棋子，并在该顶点上放置 $V_i \cdot W_i$ 个棋子。轮到玩家操作时，按照以下规则进行： 1. 选择一个非根节点、且至少有 $1$ 个棋子的顶点。 2. 选择该顶点上的一个或多个棋子，将它们移动到其**父节点**上。 无法再进行操作的玩家判负，对方获胜。每局游戏始于 Terra。 由于游戏过于简单，Terra 和 Lulu 决定进行 $Q$ 局游戏，同时按顺序执行以下两种类型的操作： - `1 x y`：将从顶点 $x$ 到顶点 $y$ 的最短路径上的每个顶点 $i$ 的乘子 $W_i$ 变为 $1 - W_i$。即 $0$ 变为 $1$，$1$ 变为 $0$。 - `2 z`：将树根更改为顶点 $z$。如果 $z$ 已经是树根，则无事发生。 每次操作后，Terra 和 Lulu 会立刻重新开始一局新游戏。对于每次操作后的一局游戏，若双方都采取最优策略，请判断最后获胜的是 Terra 还是 Lulu。所有操作均具有累计效果。

输入格式如下： > $N\ Q$ > $V_1\ V_2\ \dots\ V_N$ > $u_1\ v_1$ > $u_2\ v_2$ > $\vdots$ > $u_{N-1}\ v_{N-1}$ > $\mathrm{query}_1$ > $\mathrm{query}_2$ > $\vdots$ > $\mathrm{query}_Q$ 其中每个询问为以下两种格式之一： ``` 1 x y ``` ``` 2 z ```

对于每个执行完操作后的游戏，若 Terra 获胜输出 `Terra`，Lulu 获胜输出 `Lulu`，每行一个答案。

### 数据范围 - $2 \leq N \leq 300\,000$ - $1 \leq Q \leq 500\,000$ - $1 \leq V_i \leq 10^9$ - $1 \leq u_i, v_i \leq N$ - $1 \leq x, y, z \leq N$ - $u_i \ne v_i$ - 所有输入均为整数。 - 输入给定的图保证是一棵树。 由 ChatGPT 5 翻译