BZOJ2819 Nim

樹鍊剖分

題目傳送門

Nim遊戲中先手必勝的結論為每堆石子數的異或和不為0。

那麼這道題就變成闆子題了。

代碼：

#include<cctype>
#include<cstdio>
#include<cstring>
#include<algorithm>
#define N 500005
#define F inline
using namespace std;
struct edge{ int nxt,to; }ed[N];
struct tree{ int l,r,x; }t[N<<];
int n,m,k,p,h[N],fa[N],dep[N],tp[N],sz[N],to[N],id[N],in[N],a[N];
F char readc(){
    static char buf[],*l=buf,*r=buf;
    if (l==r) r=(l=buf)+fread(buf,,,stdin);
    return l==r?EOF:*l++;
}
F int _read(){
    int x=; char ch=readc();
    while (!isdigit(ch)&&!isupper(ch)) ch=readc();
    if (isupper(ch)) return ch;
    while (isdigit(ch)) x=(x<<)+(x<<)+(ch^),ch=readc();
    return x;
}
#define addedge(x,y) ed[++k]=(edge){h[x],y},h[x]=k
void dfs1(int x){
    dep[x]=dep[fa[x]]+,sz[x]=;
    for (int i=h[x],v;i;i=ed[i].nxt)
        if ((v=ed[i].to)!=fa[x]){
            fa[v]=x,dfs1(v),sz[x]+=sz[v];
            if (sz[to[x]]<sz[v]) to[x]=v;
        }
}
void dfs2(int x){
    if (to[in[id[x]=++p]=x]) tp[to[x]]=tp[x],dfs2(to[x]);
    for (int i=h[x],v;i;i=ed[i].nxt)
        if ((v=ed[i].to)!=fa[x]&&v!=to[x])
            tp[v]=v,dfs2(v);
}
void build(int x,int l,int r){
    t[x].l=l,t[x].r=r; int mid=l+r>>;
    if (l==r) return void(t[x].x=a[in[l]]);
    build(x<<,l,mid),build(x<<|,mid+,r);
    t[x].x=t[x<<].x^t[x<<|].x;
}
void mdfy(int x,int p,int w){
    if (t[x].l==t[x].r) return void(t[x].x=w);
    mdfy(x<<|(p>(t[x].l+t[x].r>>)),p,w);
    t[x].x=t[x<<].x^t[x<<|].x;
}
int srch(int x,int l,int r){
    if (t[x].l>r||t[x].r<l) return ;
    if (t[x].l>=l&&t[x].r<=r) return t[x].x;
    return srch(x<<,l,r)^srch(x<<|,l,r);
}
bool find(int x,int y){
    int ans=;
    while (tp[x]!=tp[y]){
        if (dep[tp[x]]<dep[tp[y]]) swap(x,y);
        ans^=srch(,id[tp[x]],id[x]),x=fa[tp[x]];
    }
    if (dep[x]<dep[y]) swap(x,y);
    return ans^srch(,id[y],id[x]);
}
int main(){
    n=_read();
    for (int i=;i<=n;i++) a[i]=_read();
    for (int i=,x,y;i<n;i++)
        x=_read(),y=_read(),addedge(x,y),addedge(y,x);
    dfs1(),tp[]=,dfs2(),build(,,n),m=_read();
    for (int f,x,y;m;m--){
        f=_read(),x=_read(),y=_read();
        if (f=='Q') puts(find(x,y)?"Yes":"No");
        else mdfy(,id[x],y);
    }
}