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=1000050,inf=0x3f3f3f3f,NULLL=N-1;

int n,m,l,op,xx,yy,zz,cnt;

int sg[N],sg_odd[N],sg_even[N];

int first[N],next[N*2],v[N*2],tot;

int root,fa[N],ch[N][2],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][0],rson=ch[x][1];

    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]&1)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][1]==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][1]==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][0]==x)^(ch[fa[y]][0]==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]+1;

    if(root)fa[x]=root,ch[root][1]=x;

    splay(x,0);

    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][0]]<=y)return find(ch[x][0],y);

    if(deep[x]<=y)return x;

    return find(ch[x][1],y);

}

int main(){

    memset(first,-1,sizeof(first));

    scanf("%d%d",&n,&l),l++;

    for(int i=1;i<=n;i++)scanf("%d",&sg[i]),sg[i]%=l;

    for(int i=1;i<n;i++)scanf("%d%d",&xx,&yy),add(xx,yy),add(yy,xx);

    d[0]=deep[0]=inf,deep[1]=1,dfs(1,0);

    fa[NULLL]=root,ch[root][1]=NULLL,splay(NULLL,0);

    scanf("%d",&m);

    for(int i=1;i<=m;i++){

        scanf("%d",&op);

        if(op==1){

            scanf("%d",&xx),xx^=cnt;

            splay(xx,0);int temp=find(ch[xx][1],deep[xx]),ans=sg[xx];

            splay(temp,xx);

            if(deep[xx]&1)ans=sg_even[ch[temp][0]];

            else ans=sg_odd[ch[temp][0]];

            if(!ans)puts("GTY");

            else puts("MeiZ"),cnt++;

        }

        else if(op==2){

            scanf("%d%d",&xx,&yy),xx^=cnt,yy^=cnt;

            splay(xx,0);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]+1;

            splay(xx,0),fa[ch[xx][1]]=yy,fa[yy]=xx;

            ch[yy][1]=ch[xx][1],ch[xx][1]=yy;

            push_up(yy),push_up(xx);

        }

    }

}