题意：
给定一棵有根树，每个节点有一些石子，每次可以将不多于k的石子移动到父节点
修改一个点的石子数，插入一个点，询问某棵子树是否先手必胜
显然是一个阶梯Nim
每次最多取k个，找规律或者观察式子易发现就是$mod (k+1)$后的Nim
问题变为：
修改点权，插入点，询问某棵子树内某一深度的点权异或和
于是放大招了：伪$ETT$
真正的ETT貌似维护的是边，欧拉遍历序列也是边组成的序列
但我们用Splay来维护欧拉遍历的点的序列，入栈出栈时都加入队列，+1，-1，好像也叫括号序列
$build$过程中保存下每个点入栈和出栈对应的Splay上的节点编号,入栈正出栈负(一开始节点编号和序列编号是一样的)
本题的子树不需要根所以询问子树只要把那段区间splay出来就行了，需要根的找出区间的前驱后继splay他们就好了
加入新节点，分配两个dfs序编号给它，把新父亲和后继splay出来然后连上再更新就行了
#include <iostream> #include <cstdio> #include <cstring> #include <algorithm> #include <cmath> using namespace std; #define lc t[x].ch[0] #define rc t[x].ch[1] #define pa t[x].fa #define pii pair<int, int> #define MP make_pair #define fir first #define sec second typedef long long ll; const int N=1e5, INF=1e9; inline int read(){ char c=getchar();int x=0,f=1; while(c<'0'||c>'9'){if(c=='-')f=-1; c=getchar();} while(c>='0'&&c<='9'){x=x*10+c-'0'; c=getchar();} return x*f; } int n, m, k, a[N], Q, op, x, y, z, id[N]; struct edge{int v, ne;} e[N<<1]; int cnt, h[N]; inline void ins(int u, int v) { e[++cnt]=(edge){v, h[u]}; h[u]=cnt; } int eul[N<<1], dfc, deep[N]; pii dfn[N]; void dfs(int u) { dfn[u].fir = ++dfc; eul[dfc]=u; for(int i=h[u];i;i=e[i].ne) deep[e[i].v] = deep[u]^1, dfs(e[i].v); dfn[u].sec = ++dfc; eul[dfc]=-u; } struct meow{int ch[2], fa, v, sg[2], deep;} t[N<<1]; int root; inline int wh(int x) {return t[pa].ch[1] == x;} inline void update(int x) { t[x].sg[0] = t[lc].sg[0]^t[rc].sg[0]; t[x].sg[1] = t[lc].sg[1]^t[rc].sg[1]; t[x].sg[t[x].deep] ^= t[x].v; } inline void rotate(int x) { int f=t[x].fa, g=t[f].fa, c=wh(x); if(g) t[g].ch[wh(f)] = x; t[x].fa=g; t[f].ch[c] = t[x].ch[c^1]; t[t[f].ch[c]].fa=f; t[x].ch[c^1]=f; t[f].fa=x; update(f); update(x); } inline void splay(int x, int tar) { for(; pa!=tar; rotate(x)) if(t[pa].fa != tar) rotate(wh(x)==wh(pa) ? pa : x); if(tar==0) root=x; } void build(int &x, int l, int r, int f) { int mid = (l+r)>>1; x=mid; t[x].fa=f; t[x].deep = deep[abs(eul[mid])]; if(eul[mid]>0) t[x].v = a[eul[mid]]; if(l<mid) build(lc, l, mid-1, x); if(mid<r) build(rc, mid+1, r, x); update(x); } int Que(int u) { int p = dfn[u].fir; splay(p, 0); int x = dfn[u].sec; splay(x, p); return t[lc].sg[deep[u]^1] > 0; } void ChaVal(int u, int d) { int x = dfn[u].fir; splay(x, 0); t[x].v = d; update(x); } inline int nex(int x) { x = rc; while(lc) x = lc; return x; } void Add(int u, int v, int d) { int p = dfn[u].fir; splay(p, 0); int x = nex(p); splay(x, p); int a = ++dfc, b = ++dfc; dfn[v] = MP(a, b); t[a].ch[1] = b; t[b].fa = a; t[a].fa = x; t[x].ch[0] = a; t[a].v = d; t[a].deep = t[b].deep = deep[v] = deep[u]^1; update(a); update(x); update(p); } int main() { freopen("in","r",stdin); n=read(); k=read()+1; for(int i=1; i<=n; i++) a[i]=read()%k, id[i]=i; for(int i=1; i<n; i++) x=read(), y=read(), ins(x, y); dfs(1); build(root, 1, dfc, 0); Q=read(); int meizi=0, ans; for(int i=1; i<=Q; i++) { op=read(); x=read()^meizi; x=id[x]; if(op==1) ans=Que(x), meizi+=ans, puts(ans ? "MeiZ" : "GTY"); else { y=read()^meizi; if(op==2) ChaVal(x, y%k); else z=(read()^meizi)%k, Add(x, id[y]=++n, z); } } return 0; }