/ 
Time Limit: 2 sec / Memory Limit: 1024 MiB
表示言語
/ /Score : 100 points
Problem Statement
Terra and Lulu are playing a board game on a tree consisting of N vertices and N-1 edges. Each vertex i of the tree has a weight V_i and a multiplier W_i. The i-th edge of the tree connects vertices u_i and v_i. Initially, all multipliers W_i are 1, and vertex 1 is the root.
When a game starts, all stones currently on each vertex i are removed, and V_i \cdot W_i stones are placed on that vertex. The players take turns performing the following action.
-
Choose a non-root vertex with at least 1 stone on it.
-
Choose one or more stones on the chosen vertex and move them to its parent vertex.
The player who can no longer perform an action loses, and the other player wins. Each game starts with Terra.
Terra and Lulu are so good at the game that they found it monotonous. They decided to play Q games while performing the following two types of queries in order.
-
1 x y: For every vertex i on the shortest path between vertices x and y, change its multiplier W_i to 1 - W_i. In other words, 0 changes to 1, and 1 changes to 0. -
2 z: Change the root of the tree to vertex z. If vertex z is already the root of the tree, nothing happens.
Each time a query is performed, Terra and Lulu start a new game from the beginning. For each of the Q games, determine who wins if both players play optimally. The effects of all queries are cumulative.
Constraints
- 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
- All given numbers are integers.
- The given graph is a tree.
Input
The input is given from Standard Input in the following format:
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
Each query is given in one of the following two formats.
1 x y
2 z
Output
For each game played after a query, output Terra if Terra wins, and Lulu if Lulu wins, one per line.
Sample Input 1
4 4 10 1 2 3 1 2 1 3 1 4 2 1 1 2 3 2 2 1 1 1
Sample Output 1
Lulu Terra Lulu Terra
表示言語
/ /Score : 100 points
문제
테라와 루루는 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
表示言語
/ /配点 : 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 つ選ぶ．
-
選んだ頂点上の石を 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
各クエリは次の 2 つの形式のいずれかで与えられる．
1 x y
2 z
出力
各クエリの後に行うゲームについて，テラが勝利するなら Terra，ルルが勝利するなら Lulu を 1 行に出力せよ．
入力例 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