计蒜客----Tree（树链剖分、按位维护）

题面：

题意：
给定一棵树，点有点权。
有以下三种操作：
（1）将 $1 - - x$ 上面的所有的点的点权都按位或上一个数 $t$ 。
（2）将 $1 - - x$ 上面的所有的点的点权都按位与上一个数 $t$ 。
（3）询问 $1 - - x$ 上面所有数的异或和。

题解：
对于 $1 - - x$ 的处理可以使用树剖处理。
对于每一位建立一棵线段树，总共是31棵线段树。线段树上维护区间中这一位为 1 的数的个数。
这样对数的处理就转化为了对每一位的单独处理。

对于某一位来说，
对于操作1，如果 $t$ 的这一位为 0，那么相当于 $1 - - x$ 节点这一位的权值未变。如果 $t$ 的这一位为 1，相当于 $1 - - x$ 节点的这一位的权值都变为 1。

对于操作2，如果 $t$ 的这一位为 0，那么相当于 $1 - - x$ 节点这一位的权值都变为0。如果 $t$ 的这一位为 1，相当于 $1 - - x$ 节点的这一位的权值未变。

对于操作3，只需要统计 $1 - - x$ 每一位的1的个数是奇数个还是偶数个即可。

时间复杂度 $O (31 * n * l o g^{2} n)$ ，有点大。

代码：

#include<iostream>
#include<cstdio>
#include<cstring>
#include<algorithm>
#include<cmath>
#include<queue>
#include<set>
#include<vector>
#define ll long long
#define llu unsigned ll
using namespace std;


char buffer[100001],*S,*T;
inline char Get_Char()
{
    if (S==T)
    {
        T=(S=buffer)+fread(buffer,1,100001,stdin);
        if (S==T) return EOF;
    }
    return *S++;
}
inline int read()
{
    char c;int re=0;
    for(c=Get_Char();c<'0'||c>'9';c=Get_Char());
    while(c>='0'&&c<='9') re=re*10+(c-'0'),c=Get_Char();
    return re;
}



const ll lnf=0x3f3f3f3f3f3f3f3f;
const int maxn=100100;
int n,m,r,k;
int head[maxn],ver[maxn<<1],nt[maxn<<1];
int f[maxn],d[maxn],si[maxn],son[maxn],rk[maxn];
int top[maxn],id[maxn],vi[maxn];
int tot=1,cnt=0;

void init(void)
{
    memset(head,0,sizeof(head));
    memset(son,0,sizeof(son));
    tot=1,cnt=0;
}

void add(int x,int y)
{
    ver[++tot]=y,nt[tot]=head[x],head[x]=tot;
}

void dfs1(int x,int fa)
{
    int max_son=0;
    si[x]=1;
    for(int i=head[x];i;i=nt[i])
    {
        int y=ver[i];
        if(y==fa) continue;
        f[y]=x;
        d[y]=d[x]+1;

        dfs1(y,x);
        si[x]+=si[y];
        if(si[y]>max_son)max_son=si[y],son[x]=y;
    }
}

void dfs2(int x,int t)
{
    top[x]=t;
    id[x]=++cnt;
    rk[cnt]=x;

    if(!son[x]) return ;
    dfs2(son[x],t);

    for(int i=head[x];i;i=nt[i])
    {
        int y=ver[i];
        if(y!=son[x]&&y!=f[x])
            dfs2(y,y);
    }
}

struct node
{
    int l,r;
    int sum;
    int laz;
}t[31][maxn<<2];

void pushup(int k,int cnt)
{
    t[k][cnt].sum=t[k][cnt<<1].sum+t[k][cnt<<1|1].sum;
}

void pushdown(int k,int cnt)
{
    if(t[k][cnt].laz!=-1)
    {
        t[k][cnt<<1].sum=(t[k][cnt<<1].r-t[k][cnt<<1].l+1)*t[k][cnt].laz;
        t[k][cnt<<1|1].sum=(t[k][cnt<<1|1].r-t[k][cnt<<1|1].l+1)*t[k][cnt].laz;
        t[k][cnt<<1].laz=t[k][cnt].laz;
        t[k][cnt<<1|1].laz=t[k][cnt].laz;
        t[k][cnt].laz=-1;
    }
}


void build(int l,int r,int k,int cnt)
{
    t[k][cnt].l=l,t[k][cnt].r=r;
    t[k][cnt].laz=-1;
    if(l==r)
    {
        t[k][cnt].sum=(vi[rk[l]]>>k)&1;
        return ;
    }

    int mid=(l+r)>>1;
    build(l,mid,k,cnt<<1);
    build(mid+1,r,k,cnt<<1|1);
    pushup(k,cnt);
}

void change(int l,int r,int val,int k,int cnt)
{
    if(l<=t[k][cnt].l&&t[k][cnt].r<=r)
    {
        t[k][cnt].sum=(t[k][cnt].r-t[k][cnt].l+1)*val;
        t[k][cnt].laz=val;
        return ;
    }

    pushdown(k,cnt);
    if(l<=t[k][cnt<<1].r) change(l,r,val,k,cnt<<1);
    if(r>=t[k][cnt<<1|1].l) change(l,r,val,k,cnt<<1|1);
    pushup(k,cnt);
}


int ask(int l,int r,int k,int cnt)
{
    if(l<=t[k][cnt].l&&t[k][cnt].r<=r)
    {
        return t[k][cnt].sum;
    }
    pushdown(k,cnt);
    int ans=0;
    if(l<=t[k][cnt<<1].r) ans+=ask(l,r,k,cnt<<1);
    if(r>=t[k][cnt<<1|1].l) ans+=ask(l,r,k,cnt<<1|1);
    return ans;
}


void change_road_or(int u,int v,int vi)
{
    for(int k=0;k<31;k++)
    {
        int val=(vi>>k)&1;
        if(val)
        {
            int x=u,y=v;
            while(top[x]!=top[y])
            {
                if(d[top[x]]<d[top[y]])
                    swap(x,y);
                change(id[top[x]],id[x],val,k,1);
                x=f[top[x]];
            }
            if(id[x]>id[y]) swap(x,y);
            change(id[x],id[y],val,k,1);
        }
    }
}

void change_road_ans(int u,int v,int vi)
{
    for(int k=0;k<31;k++)
    {
        int val=(vi>>k)&1;
        if(!val)
        {
            int x=u,y=v;
            while(top[x]!=top[y])
            {
                if(d[top[x]]<d[top[y]])
                    swap(x,y);
                change(id[top[x]],id[x],val,k,1);
                x=f[top[x]];
            }
            if(id[x]>id[y]) swap(x,y);
            change(id[x],id[y],val,k,1);
        }
    }
}

bool ask_road(int u,int v,int val)
{
    int ans=0;
    for(int k=0;k<31;k++)
    {
        int res=0;
        int x=u,y=v;
        while(top[x]!=top[y])
        {
            if(d[top[x]]<d[top[y]])
                swap(x,y);
            res=res+ask(id[top[x]],id[x],k,1);
            x=f[top[x]];
        }
        if(id[x]>id[y]) swap(x,y);
        res=res+ask(id[x],id[y],k,1);

        ans+=((res%2)<<k);
    }
    if(val==ans) return false;
    return true;
}



int main(void)
{
    while(scanf("%d%d",&n,&m)!=EOF)
    {
        init();
        int pos,x,y;
        for(int i=1;i<=n;i++)
            vi[i]=read();
        for(int i=1;i<n;i++)
        {
            x=read(),y=read();
            add(x,y);
            add(y,x);
        }
        dfs1(1,0);
        dfs2(1,1);
        for(int k=0;k<31;k++)
            build(1,cnt,k,1);
        for(int i=1;i<=m;i++)
        {
            pos=read(),x=read(),y=read();
            if(pos==1)
                change_road_or(1,x,y);
            else if(pos==2)
                change_road_ans(1,x,y);
            else
            {
                if(ask_road(1,x,y)) printf("YES\n");
                else printf("NO\n");
            }
        }
    }

    return 0;
}