BZOJ 3729 splay维护DFS序+博弈论

思路：

这像是 阶梯Nim之类的东西

我们 直接把sg函数 设成mod(L+1)的

一棵子树 向下的奇数层上的石子xor起来 就是答案

有加点和改值的操作 就splay维护一下

//By SiriusRen
#include <cstdio>
#include <cstring>
#include <algorithm>
using namespace std;
const int N=,inf=,NULLL=N-;
int n,m,l,op,xx,yy,zz,cnt;
int sg[N],sg_odd[N],sg_even[N];
int first[N],next[N*],v[N*],tot;
int root,fa[N],ch[N][],deep[N],d[N];
void add(int x,int y){v[tot]=y,next[tot]=first[x],first[x]=tot++;}
void push_up(int x){
    int lson=ch[x][],rson=ch[x][];
    d[x]=min(deep[x],min(d[lson],d[rson]));
    sg_odd[x]=sg_odd[lson]^sg_odd[rson];
    sg_even[x]=sg_even[lson]^sg_even[rson];
    if(deep[x]&)sg_odd[x]^=sg[x];
    else sg_even[x]^=sg[x];
}
void rotate(int p){
    int q=fa[p],y=fa[q],x=(ch[q][]==p);
    ch[q][x]=ch[p][!x],fa[ch[q][x]]=q;
    ch[p][!x]=q,fa[q]=p,fa[p]=y;
    if(y)ch[y][ch[y][]==q]=p;
    push_up(q);
}
void splay(int x,int tp){
    for(int y;y=fa[x];rotate(x)){
        if(y==tp)break;
        if(fa[y]!=tp){
            if((ch[y][]==x)^(ch[fa[y]][]==y))rotate(x);
            else rotate(y);
        }
    }push_up(x);
    if(!tp)root=x;
}
void dfs(int x,int y){
    if(y)deep[x]=deep[y]+;
    if(root)fa[x]=root,ch[root][]=x;
    splay(x,);
    for(int i=first[x];~i;i=next[i]){
        if(v[i]!=y)dfs(v[i],x);
    }
}
int find(int x,int y){
    if(d[ch[x][]]<=y)return find(ch[x][],y);
    if(deep[x]<=y)return x;
    return find(ch[x][],y);
}
int main(){
    memset(first,-,sizeof(first));
    scanf("%d%d",&n,&l),l++;
    for(int i=;i<=n;i++)scanf("%d",&sg[i]),sg[i]%=l;
    for(int i=;i<n;i++)scanf("%d%d",&xx,&yy),add(xx,yy),add(yy,xx);
    d[]=deep[]=inf,deep[]=,dfs(,);
    fa[NULLL]=root,ch[root][]=NULLL,splay(NULLL,);
    scanf("%d",&m);
    for(int i=;i<=m;i++){
        scanf("%d",&op);
        if(op==){
            scanf("%d",&xx),xx^=cnt;
            splay(xx,);int temp=find(ch[xx][],deep[xx]),ans=sg[xx];
            splay(temp,xx);
            if(deep[xx]&)ans=sg_even[ch[temp][]];
            else ans=sg_odd[ch[temp][]];
            if(!ans)puts("GTY");
            else puts("MeiZ"),cnt++;
        }
        else if(op==){
            scanf("%d%d",&xx,&yy),xx^=cnt,yy^=cnt;
            splay(xx,);sg[xx]=yy%l;push_up(xx);
        }
        else{
            scanf("%d%d%d",&xx,&yy,&zz);
            xx^=cnt,yy^=cnt,zz^=cnt;zz%=l;
            sg[yy]=zz,deep[yy]=deep[xx]+;
            splay(xx,),fa[ch[xx][]]=yy,fa[yy]=xx;
            ch[yy][]=ch[xx][],ch[xx][]=yy;
            push_up(yy),push_up(xx);
        }
    }
}