← 返回题目列表

AtCoder · scpc2026_div1_i

I. 树、游戏和查询

中文机器翻译题面 查看原题

表示言語

/ /

分数: 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. 选择一个至少有 1 颗石子的非根顶点。

  2. 选择该顶点上的一颗或多颗石子,并将它们移动到其 父顶点。.

无法再执行操作的玩家输,另一名玩家赢。每局游戏由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. 돌이 1개 이상 올려져 있는 루트 아닌 정점을 하나 선택한다.

  2. 선택한 정점 위에 있는 돌을 하나 이상 원하는 만큼 선택해 부모 정점 위에 올린다.

더 이상 행동을 수행할 수 없는 플레이어가 패배하고 상대편이 승리한다. 게임은 항상 테라부터 시작한다.

테라와 루루는 게임을 너무 잘하는 나머지 게임이 단조롭다고 생각했다. 테라와 루루는 다음과 같은 두 종류의 쿼리를 차례대로 수행하면서 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