题解：P10662 BZOJ4202 石子游戏

· · 题解

Solution

一眼丁真，鉴定为：不会写 Splay。

考虑本题本质上是一个阶梯博弈 + 巴什博弈。

那么我们认为一个节点的实际石子个数为 a_u \bmod (m+1)，统计节点 u 的子树中，距离它的长度为奇数的节点的实际石子个数的异或和。

在动态维护 LCT 的过程中，如果新增一个节点或者修改一个节点，把它到根这条路径上所有点都异或上新增的值。

每个点要开两个值，分别维护深度为奇数的点的异或和与深度为偶数的点的异或和。

#include<bits/stdc++.h>
#define ffor(i,a,b) for(int i=(a);i<=(b);i++)
#define roff(i,a,b) for(int i=(a);i>=(b);i--)
using namespace std;
const int MAXN=1e5+10;
int n,m,q,a[MAXN],dep[MAXN],lstans;
vector<int> G[MAXN];
struct Node {int s[2],fa,x0,x1;}t[MAXN];
struct Tag {int tg0,tg1,flp;}tag[MAXN];
void assign(int u,Tag tg) {
    if(tg.flp) swap(t[u].s[0],t[u].s[1]),tag[u].flp^=1; 
    return t[u].x0^=tg.tg0,t[u].x1^=tg.tg1,tag[u].tg0^=tg.tg0,tag[u].tg1^=tg.tg1,void();
}
void push_down(int u) {return assign(t[u].s[0],tag[u]),assign(t[u].s[1],tag[u]),tag[u]={0,0,0},void();}
void push_up(int u) {return ;}
int is_root(int u) {return u!=t[t[u].fa].s[0]&&u!=t[t[u].fa].s[1];}
int get(int u) {return u==t[t[u].fa].s[1];}
void rotate(int u) {
    int fa=t[u].fa,s=get(u),op=get(fa);
    if(!is_root(fa)) t[t[fa].fa].s[op]=u;t[u].fa=t[fa].fa;
    t[t[u].s[s^1]].fa=fa,t[fa].fa=u,t[fa].s[s]=t[u].s[s^1],t[u].s[s^1]=fa;
    return ;
}
void PUSH_DOWN(int u) {if(!is_root(u)) PUSH_DOWN(t[u].fa);return push_down(u),void();}
void splay(int u) {PUSH_DOWN(u);for(int f=t[u].fa;f=t[u].fa,!is_root(u);rotate(u)) if(!is_root(f)) rotate(get(u)==get(f)?f:u);return ;}
int access(int u) {int lst=0;while(u) splay(u),t[u].s[1]=lst,lst=u,u=t[u].fa;return lst;}
void make_root(int u) {return assign(access(u),{0,0,1}),void();}
void link(int u,int v) {return make_root(u),splay(u),t[u].s[1]=v,t[v].fa=u,void();}
void dfs(int u,int f) {
    dep[u]=dep[f]^1;
    if(f) {
        int rt;
        link(f,u),make_root(1),rt=access(u);
        if(dep[u]) assign(rt,{0,a[u],0});
        else assign(rt,{a[u],0,0});
    }
    for(auto v:G[u]) if(v!=f) dfs(v,u);
    return ;
}
int main() {
    ios::sync_with_stdio(false),cin.tie(0),cout.tie(0);
    cin>>n>>m;
    ffor(i,1,n) cin>>a[i],a[i]%=m+1;
    ffor(i,1,n-1) {int u,v;cin>>u>>v,G[u].push_back(v),G[v].push_back(u);}
    dfs(1,0);
    cin>>q;
    while(q--) {
        int op;
        cin>>op;
        if(op==1) {
            int u,val;
            cin>>u,u^=lstans;
            PUSH_DOWN(u);
            if(dep[u]) val=t[u].x0;
            else val=t[u].x1;
            if(val) cout<<"Yes\n",lstans++;
            else cout<<"No\n";
        }
        if(op==2) {
            int x,y,rt;
            cin>>x>>y,x^=lstans,y^=lstans,y%=m+1;
            make_root(1),rt=access(x);
            if(dep[x]) assign(rt,{0,a[x]^y,0});
            else assign(rt,{a[x]^y,0,0});
            a[x]=y;
        }
        if(op==3) {
            int u,v,x,rt;
            cin>>u>>v>>x,u^=lstans,v^=lstans,x^=lstans;
            dep[v]=dep[u]^1,a[v]=x%(m+1);
            link(u,v),make_root(1),rt=access(v);
            if(dep[v]) assign(rt,{0,a[v],0});
            else assign(rt,{a[v],0,0}); 
        }
    }
    return 0;
}