[BZOJ2819]Nim

Nim

题目大意

给你一棵树，实现两个操作：

1、改变制定点的权值

2、问用一条链上的所有点的权值做nim游戏，有没有必胜策略。

Solution

首先nim游戏的必胜策略：当前状态所有值异或和不是0

感性理解：每次我选择一个堆然后改变它使得异或和变成0

然后下一个玩家玩的时候不可能使异或和依旧保持0，所以就不可能变成全空的状态

那么我们用树状数组，在dfn[x]处异或上x，在dfn[x]+siz[x]处也异或上x，这样就发现在x子树内的点都异或了x而在x子树外的就没有异或x（大概是差分？）

修改的时候直接改，然后查询的时候就查询从根到x节点的链的异或和和从根到y的节点的异或和，然后从根到lca这段就相当于没有异或，但我们还要把lca的权值也给异或上

code:

#include<bits/stdc++.h>
using namespace std;
inline int lowbit(int x){return x&-x;}
int c[500010];
int n;
void update(int x,int v){
    while(x<=n+1){
        c[x]^=v;
        x+=lowbit(x);
    }
}
int query(int x){
    int ans=0;
    while(x){
        ans^=c[x];
        x-=lowbit(x);
    }
    return ans;
}
struct qwq{
    int v;
    int nxt;
}edge[1000010];
int head[500010];
int cnt=-1;
void add(int u,int v){
    edge[++cnt].nxt=head[u];
    edge[cnt].v=v;
    head[u]=cnt;
}
int dfn[500010];
int siz[500010];
int ind;
int f[500010][21];
int dep[500010];
void dfs(int u,int fa){
    for(int i=1;i<=20;++i){
        f[u][i]=f[f[u][i-1]][i-1];
    }
    siz[u]=1;
    dfn[u]=++ind;
    for(int i=head[u];~i;i=edge[i].nxt){
        int v=edge[i].v;
        if(v==fa)continue;
        f[v][0]=u;
        dep[v]=dep[u]+1;
        dfs(v,u);
        siz[u]+=siz[v];
    }
}
int lca(int x,int y){
    if(dep[x]<dep[y])swap(x,y);
    int deep=dep[x]-dep[y];
    for(int i=0;i<=20;++i){
        if(deep&(1<<i)){
            x=f[x][i];
        }
    }
    if(x==y)return x;
    for(int i=20;i>=0;--i){
        if(f[x][i]!=f[y][i]){
            x=f[x][i],y=f[y][i];
        }
    }
    return f[x][0];
}
int val[500010];
int main(){
    memset(head,-1,sizeof(head));
    scanf("%d",&n);
    for(int i=1;i<=n;++i){
        scanf("%d",&val[i]);
    }
    for(int i=1;i<n;++i){
        int u,v;
        scanf("%d%d",&u,&v);
        add(u,v),add(v,u);
    }
    dfs(1,0);
    for(int i=1;i<=n;++i){
        update(dfn[i],val[i]);
        update(dfn[i]+siz[i],val[i]);
    }
    int m;
    scanf("%d",&m);
    int mm=m;
    char ch[1];
    for(int i=1;i<=mm;++i){
        scanf("%s",ch);
        if(ch[0]=='Q'){
            int x,y;
            scanf("%d%d",&x,&y);
            int LCA=lca(x,y);
            int tmp=query(dfn[x])^query(dfn[y])^val[LCA];
            if(tmp)puts("Yes");
            else puts("No");
        }
        else {
            int x,v;
            scanf("%d%d",&x,&v);
            update(dfn[x],val[x]);
            update(dfn[x]+siz[x],val[x]);
            val[x]=v;
            update(dfn[x],val[x]);
            update(dfn[x]+siz[x],val[x]);
        }
    }
}