Description
某一天gty在与他的妹子玩游戏。 妹子提出一个游戏，给定一棵有根树，每个节点有一些石子，每次可以将不多于L的石子移动到父节点，询问
将某个节点的子树中的石子移动到这个节点先手是否有必胜策略。 gty很快计算出了策略。
但gty的妹子十分机智，她决定修改某个节点的石子或加入某个新节点。 gty不忍心打击妹子，所以他将这个问题交给了你。
另外由于gty十分绅士，所以他将先手让给了妹子。
Input
第一行两个数字，n和L,n<=5104,L<=109 第二行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。 在任意时刻，节点数不超过510^4。
Output
对于每个询问，若先手必胜，输出"MeiZ",否则输出"GTY"。
另，数据进行了强制在线处理，对于m组操作，除了类型名以外，都需要异或之前回答为"MeiZ"的个数。
Sample Input
2 1000
0 0
1 2
1
1 1
Sample Output
GTY
题解
这题被强行拼在一起…
开始是一个博弈论
先考虑一个nim模型，一堆石子，最多取m个，问你谁能赢
那么 S G [ x ] = m e x ( S G [ x ? i ] ) ( i = [ 1 , m ] ) SG[x]=mex(SG[x-i])(i=[1,m]) SG[x]=mex(SG[x?i])(i=[1,m])
找一下规律可以发现， S G [ x ] = x % ( m + 1 ) SG[x]=x\%(m+1) SG[x]=x%(m+1)
然后再套上一个阶梯博弈
结论是只需要将奇数层的 S G SG SG值异或起来
因为偶数层移到奇数层的时候下一个人可以把他移回偶数层来消除影响
但是奇数层移到偶数层的时候他可能就消失了
所以…现在只需要兹瓷一个单点插入，子树询问
单子树询问只需要dfs序一下就可以了…
但是发现要插入，也不给离线
那么另一个新姿势就是Splay维护DFS序
于是只需要知道每个点子树DFS序结束在哪里
简单考虑一下，这个点下一个不在他子树中DFS序中的点的深度一定是小于等于他的
所以我们只需要维护一个深度的min，询问的时候在树上二分即可
其他的提取区间则是Splay的基本姿势了…
就当练Splay吧
#include<cstdio>
#include<cstring>
#include<cstdlib>
#include<algorithm>
#include<cmath>
#include<queue>
#include<vector>
#include<ctime>
#include<map>
#include<bitset>
#include<set>
#define LL long long
#define mp(x,y) make_pair(x,y)
#define pll pair<long long,long long>
#define pii pair<int,int>
using namespace std;
inline LL read()
{
LL f=1,x=0;char ch=getchar();while(ch<'0'||ch>'9'){
if(ch=='-')f=-1;ch=getchar();}while(ch>='0'&&ch<='9'){
x=x*10+ch-'0';ch=getchar();}return x*f;
}
int stack[20];
inline void write(int x)
{
if(x<0){
putchar('-');x=-x;}if(!x){
putchar('0');return;}int top=0;while(x)stack[++top]=x%10,x/=10;while(top)putchar(stack[top--]+'0');
}
inline void pr1(int x){
write(x);putchar(' ');}
inline void pr2(int x){
write(x);putchar('\n');}
const int MAXN=200005;
int lin[MAXN];
struct splaytree
{
int mn,sum1,sum2,dep,cal,f,son[2];
}tr[MAXN];int tot,root;
void updata(int x)
{
int lc=tr[x].son[0],rc=tr[x].son[1];tr[x].mn=tr[x].dep;if(lc)tr[x].mn=min(tr[lc].mn,tr[x].mn);if(rc)tr[x].mn=min(tr[rc].mn,tr[x].mn);tr[x].sum1=tr[lc].sum1^tr[rc].sum1;tr[x].sum2=tr[lc].sum2^tr[rc].sum2;if(tr[x].dep&1)tr[x].sum1^=tr[x].cal;else tr[x].sum2^=tr[x].cal;
}
void rotate(int x,int w)
{
int f=tr[x].f,ff=tr[f].f;int R,r;R=f;r=tr[x].son[w];if(r)tr[r].f=R;tr[R].son[1-w]=r;R=ff;r=x;if(tr[R].son[0]==f)tr[R].son[0]=r;else tr[R].son[1]=r;tr[r].f=R;R=x;r=f;tr[R].son[w]=r;tr[r].f=R;updata(f);updata(x);
}
void splay(int x,int rt)
{
while(tr[x].f!=rt){
int f=tr[x].f,ff=tr[f].f;if(ff==rt){
if(tr[f].son[0]==x)rotate(x,1);else rotate(x,0);}else{
if(tr[ff].son[0]==f&&tr[f].son[0]==x)rotate(f,1),rotate(x,1);else if(tr[ff].son[1]==f&&tr[f].son[0]==x)rotate(x,1),rotate(x,0);else if(tr[ff].son[1]==f&&tr[f].son[1]==x)rotate(f,0),rotate(x,0);else rotate(x,0),rotate(x,1);}}if(rt==0)root=x;
}
int nxt[MAXN],pre[MAXN];
void add(int f)
{
splay(nxt[f],0);splay(f,nxt[f]);pre[nxt[f]]=tot;nxt[tot]=nxt[f];nxt[f]=tot;pre[tot]=f;tr[f].son[1]=tot;tr[tot].f=f;splay(tot,0);
}
int n,L;
struct edge{
int x,y,next;}a[MAXN];int len,last[MAXN];
void ins(int x,int y){
len++;a[len].x=x;a[len].y=y;a[len].next=last[x];last[x]=len;}int in[MAXN],fac[MAXN],ru[MAXN],dep[MAXN],dfn;
void pre_tree_node(int x,int fa)
{
in[x]=++dfn;fac[dfn]=x;for(int k=last[x];k;k=a[k].next){
int y=a[k].y;if(y!=fa)dep[y]=dep[x]+1,pre_tree_node(y,x);}
}
void newnode(int dep,int cal,int op)
{
tr[op].dep=dep;tr[op].cal=cal;updata(op);
}
int init(int l,int r)
{
if(l>r)return 0;if(l==r){
newnode(dep[fac[l]],lin[fac[l]],fac[l]);return fac[l];}int mid=(l+r)/2;int lc=init(l,mid-1),rc=init(mid+1,r);newnode(dep[fac[mid]],lin[fac[mid]],fac[mid]);tr[fac[mid]].son[0]=lc;tr[fac[mid]].son[1]=rc;if(lc)tr[lc].f=fac[mid];if(rc)tr[rc].f=fac[mid];updata(fac[mid]);return fac[mid];
}
int fd(int x,int rt)
{
if(!tr[x].son[1])return x;x=tr[x].son[1];while(x){
int lc=tr[x].son[0],rc=tr[x].son[1];if(tr[x].dep<=tr[rt].dep){
if(!lc||tr[lc].mn>tr[rt].dep)return pre[x];else x=lc;}else{
if(!lc||tr[lc].mn>tr[rt].dep){
if(!rc)return x;x=rc;}else x=lc;}}
}
map<int,int> mp;
int main()
{
n=read();L=read();for(int i=1;i<=n;i++)lin[i]=read()%(L+1);for(int i=1;i<n;i++){
int x=read(),y=read();ins(x,y);ru[y]++;}for(int i=1;i<=n;i++)if(!ru[i])pre_tree_node(i,0);root=init(1,n);for(int i=1;i<n;i++)nxt[fac[i]]=fac[i+1];for(int i=1;i<=n;i++)pre[fac[i]]=fac[i-1],mp[i]=i;pre[200000]=fac[n];nxt[fac[n]]=200000;pre[fac[1]]=200001;nxt[200001]=fac[1];splay(fac[n],0);tr[200000].f=fac[n];tr[200000].dep=-1;tr[fac[n]].son[1]=200000;updata(fac[n]);tot=n;splay(fac[1],0);tr[200001].f=fac[1];tr[200001].dep=-1;tr[fac[1]].son[0]=200001;updata(fac[1]);int Q=read(),lastans=0;while(Q--){
int opt=read(),u=read()^lastans;if(opt==1){
u=mp[u];splay(u,0);int lst=fd(u,u);splay(nxt[lst],0);splay(pre[u],nxt[lst]);u=tr[pre[u]].son[1];if(tr[u].dep&1){
if(tr[u].sum2)puts("MeiZ"),lastans++;else puts("GTY");}else{
if(tr[u].sum1)puts("MeiZ"),lastans++;else puts("GTY");}}else if(opt==2){
int cal=read()^lastans;u=mp[u];splay(u,0);tr[u].cal=cal%(L+1);updata(u);}else{
u=mp[u];int son=read()^lastans,cal=read()^lastans;tot++;mp[son]=tot;son=mp[son];tr[son].dep=tr[u].dep+1;tr[son].cal=cal%(L+1);add(u);}}return 0;
}