E - Tree

题目链接

题意

两个人玩游戏，每次有几堆石头，每个人可以选一堆石头，从里面拿走任意个，最后没有石头拿的人输。（这个博弈，经典的nim博弈）
现在有一棵树，有点权，有三种操作，
1 s t 1 ~ s路径上的节点的权值变为ai | t
2 s t 1 ~ s路径上的节点的权值变为ai & t
3 s t 用1 ~ s路径上的节点另加一堆t个石头来玩游戏，问先手的人会不会赢。
博弈跟这棵树没关系，只是用一下树的点权。。。

题解

nim博弈：
每堆石头有a1 a2 a3 …… ak个
那么如果a1 ^ a2 ^ a3 ^ …… ^ ak == 0的话先手胜利。
这样的话题就变成了一棵树上询问这条路径上的点权异或和是不是等于t。
有修改路径上的点权，就线段树维护了。。
先树刨，然后建线段树维护权值，
具体怎么维护呢？因为最后要求的是异或值，但是修改的是 | 或 &
所以只存一个数值是没法维护的（我不会），
可以维护他的二进制的每一位，这样的话，如果这个区间里某一位的数量是奇数个，那么异或的答案就包含这个值。
修改：
| t这一位是1的话，这一位都变为1
& t这一位是0的话，这一位就都变为0

代码：

#include <algorithm>
#include <cstdio>
#include <iostream>
#include <vector>
#include <stack>
#include <queue>
#include <map>
#include <cmath>
#include <set>
#include <cstring>
#include <string>
#include <bitset>
#include <stdlib.h>
#include <time.h>
using namespace std;
typedef long long ll;
typedef pair<int,int> pii;
typedef pair<ll,ll> pll;
typedef unsigned long long ull;
typedef set<int>::iterator sit;
#define st first
#define sd second
#define mkp make_pair
#define pb push_back
void wenjian(){
   freopen("concatenation.in","r",stdin);freopen("concatenation.out","w",stdout);}
void tempwj(){
   freopen("hash.in","r",stdin);freopen("hash.out","w",stdout);}
ll gcd(ll a,ll b){
   return b == 0 ? a : gcd(b,a % b);}
ll qpow(ll a,ll b,ll mod){
   a %= mod;ll ans = 1;while(b){
   if(b & 1)ans = ans * a;a = a * a;b >>= 1;}return ans;}
ll qpowm(ll a,ll b){
   ll ans = 1;while(b){
   if(b & 1)ans = ans * a;a = a * a;b >>= 1;}return ans;}

struct cmp{
   bool operator()(const pii & a, const pii & b){
   return a.st < b.st;}};
int lb(int x){
   return  x & -x;}
/* friend bool operator < (Node a,Node b) { return a.val > b.val; */
const int inf = 0x3f3f3f3f;
const ll INF = 0x3f3f3f3f3f3f3f3f;
const ll mod = 1e9+9;
const int maxn = 1e5 + 5;
int a[maxn];
int fa[maxn];
int son[maxn];
int siz[maxn];
vector<int> vv[maxn];
void dfs1(int x,int father)
{
   
    fa[x] = father;
    siz[x] = 1;
    son[x] = 0;
    for (int i = 0; i < vv[x].size() ; i++ )
    {
   
        int v = vv[x][i];
        if(v == father)
            continue;
        dfs1(v,x);
        siz[x] += siz[v];
        if(siz[v] > siz[son[x]])
            son[x] = v;
    }
    //printf("%d %d\n",x,son[x]);
}
int pos = 0;
int top[maxn];
int p[maxn];
int fp[maxn];
void dfs2(int x,int tdp)
{
   
    top[x] = tdp;
    p[x] = ++pos;
    fp[pos] = x;
    if(son[x] == 0)
        return;
    dfs2(son[x],tdp);
    for (int i =0 ; i < vv[x].size(); i ++ )
    {
   
        int v = vv[x][i];
        if(v == fa[x] || v == son[x])
            continue;
        dfs2(v,v);
    }
}
struct Node
{
   
    int l,r,num[32];
    int tag[32];
}node[maxn<<2];
void up(int no)
{
   
    for (int i = 0; i <= 31; i ++ )
    {
   
        node[no].num[i] = node[no<<1].num[i] + node[no<<1|1].num[i];
    }
}
void build(int l,int r,int no)
{
   
    node[no].l = l;
    node[no].r = r;
    if(l == r)
    {
   
        for (int i = 0; i <= 31; i ++ )
        {
   
            node[no].num[i] = a[fp[l]] >> i & 1;
        }
        return;
    }
    int mid = l + r>>1;
    build(l,mid,no<<1);
    build(mid + 1,r,no<<1|1);
    up(no);
}
void down(int no)
{
   
    for (int i =0 ; i <=31; i ++ )
    {
   
        if(node[no].tag[i] == 1)
        {
   
            node[no<<1].tag[i] = 1;
            node[no<<1|1].tag[i] = 1;
            node[no<<1|1].num[i] = node[no<<1|1].r - node[no<<1 | 1].l + 1;
            node[no<<1].num[i] = node[no <<1].r - node[no << 1].l  + 1;
        }
        else if(node[no].tag[i] == -1)
        {
   
            node[no<<1].tag[i] = -1;
            node[no<<1].num[i] = 0;
            node[no<<1|1].tag[i] = -1;
            node[no<<1|1].num[i] = 0;
        }

        node[no].tag[i] = 0 ;
    }
}
void update(int l,int r,int no,int f,int x)
{
   
    if(node[no].l >r || node[no].r < l)
        return;
    if(node[no].l >= l && node[no].r <= r)
    {
   
        for(int i = 0; i <= 31; i ++ )
        {
   
            if(x >> i & 1)
            {
   
                if(f == 1)
                {
   
                    node[no].tag[i] = 1;
                    node[no].num[i] = node[no].r - node[no].l + 1;
                }
            }
            else
            {
   
                if(f == 2)
                {
   
                    node[no].num[i] = 0;
                    node[no].tag[i] = -1;
                }
            }
        }
        return;
    }
    down(no);
    update(l,r,no<<1,f,x);
    update(l,r,no<<1|1,f,x);
    up(no);
}
int query(int l,int r,int no)
{
   
    if(node[no].l > r || node[no].r < l)
        return 0;
    if(node[no].l >= l && node[no].r <= r)
    {
   
        int ans =0 ;
        for(int i =0 ; i < 32; i ++ )
        {
   
            if(node[no].num[i] % 2)
                ans += 1 << i;
        }
        return ans;
    }
    down(no);
    return query(l,r,no<<1) ^ query(l,r,no<<1|1);
}

void change(int x,int num,int f)
{
   
    int k = top[x];
    while(k != 1)
    {
   
        update(p[k],p[x],1,f,num);
        x = fa[k];
        k = top[x];
    }
    update(p[1],p[x],1,f,num);
}
int getans(int x)
{
   
    int ans = 0;
    int k = top[x];
    while(k !=1)
    {
   
        //printf("%d\n",k);
        ans ^= query(p[k],p[x],1);
        x = fa[k];
        k = top[x];
    }
    ans ^= query(p[1],p[x],1);
    return ans;
}
int main()
{
   
    int n,m;
    scanf("%d%d",&n,&m);
    for (int i = 1; i <= n; i ++ )
        scanf("%d",&a[i]);
    for (int i = 1; i < n;  i++ )
    {
   
        int x,y;
        scanf("%d%d",&x,&y);
        vv[x].pb(y);
        vv[y].pb(x);
    }
    dfs1(1,0);
    dfs2(1,1);
    build(1,n,1);
   // printf("11111111\n");
    while(m -- )
    {
   
        int f,s,t;
        scanf("%d%d%d",&f,&s,&t);
        if(f == 1 || f == 2)
        {
   
            change(s,t,f);
        }
        else
        {
   
            int ans = getans(s);
            if(ans == t)
                printf("NO\n");
            else
                printf("YES\n");
        }
    }
}