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
题解： 首先，要知道阶梯博弈，就会发现这个题里偶数层的石子动了白动，因为别人可以把它移到奇数层。关键是有个插入操作，这就需要splay维护dfs序了。由于序列是动态的，所以我们需要动态维护每个点的size。 不过简单点想，一个节点所掌管的区间就是这个节点为左端点，节点右边第一个深度小于等于它自己的那个点为右端点。 于是我们可以维护区间min_dep值。 然后维护深度为奇数和偶数的层数的异或和。 似乎可以用树分块？？gty系列好像都可以。 话说，我们机房有个gty==
#include<map> #include<math.h> #include<stdio.h> #include<vector> #include<string.h> #include<iostream> #include<algorithm> #define inf 0x3f3f3f3f #define ll long long #define N 100005 using namespace std; int read() { int x=0,f=1; 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 n,m,mod; int rt,ind,ynum,top; int val[N<<1],fa[N<<1],ch[N<<1][2],typ[N<<1],sg[N<<1][2]; int a[N],st[N],dep[N],pos[N][2]; map<int,int> id; vector<int> e[N]; void pushup(int x) { int l=ch[x][0],r=ch[x][1]; sg[x][0]=sg[l][0]^sg[r][0]; sg[x][1]=sg[l][1]^sg[r][1]; sg[x][typ[x]]^=val[x]; } void rotate(int x,int &k) { int y=fa[x],z=fa[y],l,r; l=(ch[y][1]==x);r=l^1; if(y==k) k=x; else ch[z][ch[z][1]==y]=x; fa[ch[x][r]]=y,fa[y]=x,fa[x]=z; ch[y][l]=ch[x][r],ch[x][r]=y; pushup(y),pushup(x); } void splay(int x,int &k) { while(x!=k) { int y=fa[x],z=fa[y]; if(y!=k) { if(ch[y][0]==x^ch[z][0]==y) rotate(x,k); else rotate(y,k); } rotate(x,k); } } int build(int l,int r,int f) { if(l>r) return 0; int mid=l+r>>1; if(st[mid]>0) { val[mid]=a[st[mid]]; pos[st[mid]][0]=mid; } else pos[-st[mid]][1]=mid; typ[mid]=dep[abs(st[mid])]; fa[mid]=f; ch[mid][0]=build(l,mid-1,mid),ch[mid][1]=build(mid+1,r,mid); pushup(mid); return mid; } void insert(int u,int v,int num) { splay(pos[u][0],rt); int t=ch[rt][1]; while(ch[t][0]) t=ch[t][0]; int t1=++top,t2=++top; pos[v][0]=t1,pos[v][1]=t2; fa[t1]=t,fa[t2]=t1; ch[t][0]=t1,ch[t1][1]=t2; val[t1]=num,typ[t1]=typ[t2]=dep[v]; pushup(t2),pushup(t1); splay(t2,rt); } void query(int x) { splay(pos[x][0],rt),splay(pos[x][1],ch[rt][1]); if(sg[ch[pos[x][1]][0]][dep[x]^1]) { ynum++; puts("MeiZ"); } else puts("GTY"); } void dfs(int x) { st[++top]=x; for(int i=0;i<e[x].size();i++) { dep[e[x][i]]=dep[x]^1; dfs(e[x][i]); } st[++top]=-x; } int main() { n=read(),mod=read()+1; for(int i=1;i<=n;i++) { a[i]=read()%mod; id[i]=i; } for(int i=1;i<n;i++) { int u=read(),v=read(); e[u].push_back(v); } dfs(1); rt=build(1,top,0); m=read(); int opt,u,v,x; while(m--) { opt=read(); if(opt==1) { v=read()^ynum; query(id[v]); } if(opt==2) { x=read()^ynum; v=(read()^ynum)%mod; x=id[x]; splay(pos[x][0],rt); val[rt]=v; pushup(rt); } if(opt==3) { u=read()^ynum,v=read()^ynum,x=read()^ynum; u=id[u]; id[v]=++n; dep[id[v]]=dep[u]^1; insert(u,id[v],x%mod); } } return 0; }