F.A.Qs Home Discuss ProblemSet Status Ranklist Contest 入门OJ LoginRegister 捐赠本站
Notice:1:注册本OJ方式请见https://www.lydsy.com/JudgeOnline/wttl/thread.php?tid=5671 2:请不要在讨论区中发空白主题帖。
Problem 3729. -- Gty的游戏

3729: Gty的游戏

Time Limit: 20 Sec  Memory Limit: 128 MB
Submit: 1009  Solved: 358
[Submit][Status][Discuss]

Description

某一天gty在与他的妹子玩游戏。
妹子提出一个游戏,给定一棵有根树,每个节点有一些石子,每次可以将不多于L的石子移动到父节点,询问
将某个节点的子树中的石子移动到这个节点先手是否有必胜策略。
gty很快计算出了策略。
但gty的妹子十分机智,她决定修改某个节点的石子或加入某个新节点。
gty不忍心打击妹子,所以他将这个问题交给了你。
另外由于gty十分绅士,所以他将先手让给了妹子。

Input

第一行两个数字,n和L,n<=5*10^4,L<=10^9
第二行n个数字,表示每个节点初始石子数。
接下来n-1行,每行两个整数u和v,表示有一条从u到v的边。
接下来一行一个数m,表示m组操作。
接下来m行,每行第一个数字表示操作类型
若为1,后跟一个数字v,表示询问在v的子树中做游戏先手是否必胜。
若为2,后跟两个数字x,y表示将节点x的石子数修改为y。
若为3,后跟三个数字u,v,x,表示为u节点添加一个儿子v,初始石子数为x。
在任意时刻,节点数不超过5*10^4。

Output

对于每个询问,若先手必胜,输出"MeiZ",否则输出"GTY"。
另,数据进行了强制在线处理,对于m组操作,除了类型名以外,都需要异或之前回答为"MeiZ"的个数。

Sample Input

2 1000
0 0
1 2
1
1 1

Sample Output

GTY

HINT

Source

By wangxz

[Submit][Status][Discuss]

HOME Back