正题

题目链接:https://darkbzoj.tk/problem/3729

题目大意

给出\(n\)个点的一棵树，第\(i\)个节点上有\(a_i\)个石子，然后每次可以选择不超过\(L\)个石子移动到父节点处。要求支持操作

• 以一个节点的子树进行博弈是否有先手必胜
• 修改一个节点的石子个数
• 插入一个新的叶子

\(1\leq n,m\leq 5\times 10^4,1\leq L\leq 10^9\)

解题思路

额，首先是阶梯博弈和巴什博弈的缝合怪

巴什博弈结论是石头直接模上一个\(L+1\)，然后阶梯博弈要分奇偶深度

然后不带插入的话就是维护\(dfs\)序区间的奇数深度和偶数深度的异或和就好了，但是要插入所以要一次改一堆\(dfs\)序，所以要用\(Splay\)维护就好了。

时间复杂度\(O(m\log n)\)

code

#include<cstdio>
#include<cstring>
#include<algorithm>
using namespace std;
const int N=2e5+10;
struct node{
int to,next;
}a[N<<1];
int n,m,L,tot,ls[N],dep[N],v[2][N];
int t[N][2],fa[N],w[2][N],d[N],last;
bool Direct(int x)
{return t[fa[x]][1]==x;}
void PushUp(int x){
if(!x)return;
w[0][x]=v[0][x]^w[0][t[x][0]]^w[0][t[x][1]];
w[1][x]=v[1][x]^w[1][t[x][0]]^w[1][t[x][1]];
d[x]=min(dep[x],min(d[t[x][0]],d[t[x][1]]));
return;
}
void Rotate(int x){
int y=fa[x],z=fa[y];
int xs=Direct(x),ys=Direct(y);
int w=t[x][xs^1];
t[x][xs^1]=y;t[y][xs]=w;
if(z)t[z][ys]=x;
if(w)fa[w]=y;fa[y]=x;fa[x]=z;
PushUp(y);PushUp(x);return;
}
void Splay(int x,int f){
while(fa[x]!=f){
int y=fa[x];
if(fa[y]==f)Rotate(x);
else if(Direct(x)==Direct(y))
Rotate(y),Rotate(x);
else Rotate(x),Rotate(x);
}
return;
}
int Find(int x,int k){
if(d[t[x][0]]<=k)Find(t[x][0],k);
if(dep[x]<=k)return x;
return Find(t[x][1],k);
}
void addl(int x,int y){
a[++tot].to=y;
a[tot].next=ls[x];
ls[x]=tot;return;
}
void dfs(int x,int F){
t[last][1]=x;fa[x]=last;
last=x;dep[x]=dep[F]+1;
if(dep[x]&1)swap(v[0][x],v[1][x]);
for(int i=ls[x];i;i=a[i].next){
int y=a[i].to;
if(y==F)continue;
dfs(y,x);
}
return;
}
void Downdata(int x)
{PushUp(x);if(fa[x])Downdata(fa[x]);return;}
int main()
{
freopen("1.in","r",stdin);
freopen("1.out","w",stdout);
scanf("%d%d",&n,&L);d[0]=n+1;
for(int i=1;i<=n;i++)scanf("%d",&v[0][i]),v[0][i]%=(L+1);
for(int i=1;i<n;i++){
int x,y;
scanf("%d%d",&x,&y);
addl(x,y);addl(y,x);
}
last=N-1;d[N-1]=dep[N-1]=n+1;
dfs(1,0);t[last][1]=N-2;fa[N-2]=last;
last=N-2;d[N-2]=dep[N-2]=n+1;
Downdata(last);
int sum=0;
scanf("%d",&m);
for(int i=1;i<=m;i++){
int op,z,x,y;
scanf("%d",&op);
if(op==1){
scanf("%d",&x);x^=sum;
if(i==106)
i++,i--;
Splay(x,0);
if(d[t[x][1]]>dep[x]){
if(w[(dep[x]&1)^1][t[x][1]])
puts("MeiZ"),sum++;
else
puts("GTY");
}
else{
y=Find(t[x][1],dep[x]);
Splay(y,x);
if(w[(dep[x]&1)^1][t[y][0]])
puts("MeiZ"),sum++;
else
puts("GTY");
}
}
else if(op==2){
scanf("%d%d",&x,&y);
x^=sum;y^=sum;Splay(x,0);
v[dep[x]&1][x]=y%(L+1);PushUp(x);
}
else if(op==3){
scanf("%d%d%d",&x,&y,&z);
z^=sum;x^=sum;y^=sum;
dep[y]=dep[x]+1;v[dep[y]&1][y]=z%(L+1);
PushUp(y);Splay(x,0);
int k=t[x][1];while(t[k][0])k=t[k][0];
Splay(k,x);fa[y]=k;t[k][0]=y;
PushUp(k);PushUp(x);
}
}
return 0;
}