表示言語
/ /分数: 100 点
问题陈述
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 颗石子的非根顶点。
-
选择该顶点上的一颗或多颗石子,并将它们移动到其 父顶点。.
无法再执行操作的玩家输,另一名玩家赢。每局游戏由Terra开始。
Terra和Lulu非常擅长这款游戏,以至于他们觉得它很单调。他们决定玩 Q 游戏,同时按顺序执行以下两种类型的查询。
-
1 x y:对于每个顶点 i 在顶点之间的最短路径上 x 和 y,改变其倍增器 W_i to 1 - W_i。换句话说, 0 更改为 1,和 1 更改为 0. -
2 z:将树的根更改为顶点 z。如果顶点 z 已经是树的根,则不会发生任何情况。
每次执行查询时,Terra 和 Lulu 都从头开始一局新游戏。对于每一局 Q 游戏,如果两位玩家都进行最优游戏,确定谁获胜。所有查询的效应是累积的。
约束
- 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
- 所有给定的数字都是整数。
- 给定的图是一棵树。
输入
输入由标准输入按以下格式给出:
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 如果泰拉获胜,并且 Lulu 如果露露赢了,每行一个。
示例输入 1
4 4 10 1 2 3 1 2 1 3 1 4 2 1 1 2 3 2 2 1 1 1
示例输出 1
Lulu Terra Lulu Terra
表示言語
/ /分数: 100 点
문제
테라와 루루는 N개의 정점과 N-1개의 간선으로 이루어진 트리 위에서 보드게임을 하고 있다. 트리의 각 정점 i마다 가중치 V_i와 배수 W_i가 있다. 트리의 i번째 간선은 두 정점 u_i와 v_i를 연결한다. 처음에 모든 배수 W_i는 1이고 1번 정점이 루트 정점이다.
게임이 시작되면 각 정점 i에 있던 돌을 치우고 V_i \cdot W_i개의 돌을 올린다. 각 플레이어가 번갈아 가며 다음 행동을 수행한다.
-
돌이 1개 이상 올려져 있는 루트 아닌 정점을 하나 선택한다.
-
선택한 정점 위에 있는 돌을 하나 이상 원하는 만큼 선택해 부모 정점 위에 올린다.
더 이상 행동을 수행할 수 없는 플레이어가 패배하고 상대편이 승리한다. 게임은 항상 테라부터 시작한다.
테라와 루루는 게임을 너무 잘하는 나머지 게임이 단조롭다고 생각했다. 테라와 루루는 다음과 같은 두 종류의 쿼리를 차례대로 수행하면서 Q번의 게임을 진행하기로 했다.
-
1 x y: x번 정점과 y번 정점을 잇는 최단 경로 위에 존재하는 모든 정점 i의 배수 W_i를 1 - W_i로 변경한다. 즉, 0은 1로, 1은 0으로 바뀐다. -
2 z: z번 정점을 트리의 루트로 변경한다. z번 정점이 이미 트리의 루트라면 아무 일도 일어나지 않는다.
각 쿼리를 수행할 때마다 테라와 루루는 처음부터 게임을 시작한다. 두 플레이어가 승리하기 위해 최선을 다할 때 Q번의 게임마다 누가 승리하는지 구해 보자. 모든 쿼리의 효과는 누적된다.
제한
- 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
- 주어지는 모든 수는 정수이다.
- 주어지는 그래프는 트리이다.
입력
입력은 다음 형식으로 표준 입력으로 주어진다.
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, 루루가 승리한다면 Lulu를 한 줄에 하나씩 출력한다.
입력 예 1
4 4 10 1 2 3 1 2 1 3 1 4 2 1 1 2 3 2 2 1 1 1
출력 예 1
Lulu Terra Lulu Terra