月考已挂，人生无望……

在政治考试的最后十分钟想到了这题的做法，于是昨天中午就开始坑这题。结果真是太tmd的操蛋了！是不是我每一次打LCT都要出一些莫名其妙的状况！本来打算昨天晚上坑出来的，结果由于会考报名，浪费了将近一个小时的时间，最后还是没有坑出来……TAT

 

这道题是树上的阶梯博弈（Staircase Nim），一条链版本的阶梯博弈是这样的：每一次可以将一个结点上的任意块石头移动到编号比其恰好小1的结点上，最多只能移到编号为1的结点，第一个不能够移的就输了，问先手有无必胜策略。从编号为奇数的结点（距离1号结点的距离为偶数）把石子往上移，则另一个人可以把这石头再往上移，等于是没有移动，所以不需要考虑这种情况，所以，只需要考虑编号为偶数的结点，将编号为偶数的结点的所有石头数目都异或起来，如果是0则后手必胜否则先手必胜（具体的请详见任意的博弈论和SG函数论文）。

树上也是差不多的，对于一棵有根树，假设根的深度为1，那么只需要求出所有深度为偶数的结点上的石头数目的异或值，如果为0则后手必胜，否则先手必胜。

如果只有查询操作，那么只需要dfs一遍全树预处理出每个结点的答案就可以了，但是，有修改操作。

我们发现，修改一个权值的结点，影响的是所有与其距离为奇数的祖先结点，那么就可以先树链剖分一下，然后用线段树维护，在政治考试的时候，我想到的是用两棵线段树维护，一棵维护以1为根时，深度为奇数的结点，一棵维护深度为偶数的结点，修改一个结点x的权值，如果dep[x]为奇数，则在第二棵线段树上打标记，否则在第一棵线段树上打标记。想法是很好的……直到我想起来还有加点的操作……QAQ

所以只能用动态树维护，加入一个结点和修改结点的权值都将其父亲节点到根节点的链给凸显出来，然后打个标记，开始的时候我打的标记是lazy&&k，表示dep&1==k的就异或一下lazy，然后可能有些问题，后来被我改成lazy[2]了，剩下的就是细节问题了。

自从上次CF Round #275 1E被坑了之后，我打平衡树都是打struct+指针了，这一次也一样。打的还是挺顺溜的，就是不知道什么地方出了问题，调得欲仙欲死。

后来发现，原来应该要模(L+1)的……改掉之后还是出了问题，发现rotate的时候，打的是z->son[1]=y……最后应该是没有问题了吧？然后就TLE了……现在想想，估计是因为每一次，将一个点到根节点的那条链凸显出来的时候，都是这么干的缘故吧:v[1]->access(),v[1]->splay()。于是，把v[1]->splay()去掉之后，好像就AC了（我也不知道是不是因为去掉了这句话，想来想去，我最后一次改掉的代码中也就只有这个是最有可能的了）……

 

#include <cstdio>
#include <algorithm>
#include <iostream>
#include <cstring>
#include <cstdlib>
#include <utility>
#include <bitset>
#include <vector>
#include <string>
#include <stack>
#include <queue>
#include <ctime>
#include <cmath>
#include <list>
#include <map>
#include <set>
using namespace std;
typedef long long ll;
typedef double D;
typedef pair<int,int> pr;
const int infi=2147483647;
const D eps=1e-6;
const D pi=acos(-1.0);
const int N=300010;
struct LCT* null;
struct LCT{
    LCT* fa;
    LCT* son[2];
    int ans,w,d,lazy[2];
    void newnode(int _w=0,int _d=0) {
        fa=son[0]=son[1]=null;
        ans=lazy[0]=lazy[1]=0; w=_w; d=_d;
    }
    bool isroot() {return (fa==null)||(fa->son[0]!=this&&fa->son[1]!=this);}
    void rotate() {
        LCT *x=this,*y=x->fa,*z=y->fa;
        int w=(y->son[0]==x);
        if (!y->isroot()) {
            if (z->son[0]==y) z->son[0]=x;
            if (z->son[1]==y) z->son[1]=x;
        } x->fa=y->fa; y->fa=x;
        if (x->son[w]!=null) x->son[w]->fa=y;
        y->son[w^1]=x->son[w]; x->son[w]=y; 
    }
    void add(int x,int y) {
        LCT *t=this;
        if (t==null) return;
        if (t->d==y) t->ans^=x;
        t->lazy[y]^=x;
    }
    void clean() {
        if (this==null) return;
        if (lazy[0]) {
            son[0]->add(lazy[0],0);
            son[1]->add(lazy[0],0);
            lazy[0]=0;
        }
        if (lazy[1]) {
            son[0]->add(lazy[1],1);
            son[1]->add(lazy[1],1);
            lazy[1]=0;
        }
    }
    void clear() {
        if (this==null) return;
        if (!isroot()) fa->clear();
        this->clean();
    }
    void splay() {
        LCT *x=this,*y,*z;
        x->clear();
        while (!x->isroot()) {
            y=x->fa; z=y->fa;
            if (!y->isroot()) 
                if ((z->son[0]==y)^(y->son[1]==x)) y->rotate();
                else x->rotate();
            x->rotate();
        }
    }
    void access() {
        LCT *y=null,*x=this;
        for (;x!=null;y=x,x=x->fa) {
            x->splay();
            x->son[1]=y;
        }
    }
};
LCT pool[N];
LCT* v[N];
LCT* cur;
int n,m,mod,last,fa[N];
int g[N],to[N],nxt[N],tot;
void read(int &a) {
    char ch; while (!((ch=getchar())>='0'&&ch<='9'));
    a=ch-'0'; while ((ch=getchar())>='0'&&ch<='9') (a*=10)+=ch-'0';
}
void init() {
    cur=pool; null=cur++;
    null->newnode();
}
void addedge(int x,int y) {
    to[++tot]=y; nxt[tot]=g[x]; g[x]=tot;
    to[++tot]=x; nxt[tot]=g[y]; g[y]=tot;
}
void addnew(int x,int y) {
    v[1]->access();
    v[x]->access();
    v[x]->splay();
    v[x]->add(v[y]->w,v[x]->d);
    v[y]->access();
    v[y]->splay();
    v[y]->fa=v[x];
    v[y]->access();
    v[y]->splay();
}
void dfs(int x,int fat,int dep) {
    v[x]->d=dep; fa[x]=fat;
    if (fat) addnew(fat,x);
    for (int k=g[x];k;k=nxt[k]) 
        if (to[k]!=fat) dfs(to[k],x,dep^1);
}
bool ask(int x) {
    v[x]->access();
    v[x]->splay();
    return v[x]->ans!=0;
}
void change(int x,int c) {
    int y=fa[x];
    if (x!=1) {
        v[1]->access();
        v[y]->access();
        v[y]->splay();
        v[y]->add(v[x]->w^c,v[y]->d);
    } v[x]->w=c;
}
int main() {
    int i,k,x,y,z;
    read(n); read(mod); init();
    for (i=1;i<=n;i++) v[i]=cur++;
    for (i=1;i<=n;i++) {
        read(x); v[i]->newnode(x%(mod+1));
    }
    for (i=1;i<n;i++) {
        read(x); read(y);
        addedge(x,y);
    } dfs(1,0,1);
    for (read(m),i=1;i<=m;i++) {
        read(k);
        if (k==1) {
            read(x); x^=last;
            if (ask(x)) puts("MeiZ"),last++;
            else puts("GTY");
        } else if (k==2) {
            read(x); read(y);
            x^=last; y^=last;
            change(x,y%(mod+1));
        } else if (k==3) {
            read(x); read(y); read(z);
            x^=last; y^=last; z^=last;
            v[y]=cur++; fa[y]=x;
            v[y]->newnode(z%(mod+1),v[x]->d^1);
            addnew(x,y);
        }
    }
    return 0;
}