题目：https://www.lydsy.com/JudgeOnline/problem.php?id=4811
因为位运算的结果有可合并性，所以可以树链剖分，线段树维护；
细节很多，特别要注意从左往右运算和从右往左计算是不同的，在不同条件下一定要区分！！！
这篇博客写得很好(我就是模仿它写的)：https://blog.csdn.net/a1799342217/article/details/78818480
代码如下：
#include<iostream> #include<cstdio> #include<cstring> using namespace std; typedef unsigned long long ull; int const maxn=100005; int n,m,p,in[maxn],id[maxn],to[maxn],tp[maxn],head[maxn],ct,dep[maxn],fa[maxn],siz[maxn],tim; ull op[maxn][3]; struct N{ int to,next; N(int t=0,int n=0):to(t),next(n) {} }edge[maxn<<1]; struct data{ull p0,p1;}tr[maxn<<2],tl[maxn<<2]; struct T{int l,r;}t[maxn<<2]; void add(int x,int y){edge[++ct]=N(y,head[x]);head[x]=ct;} void dfs1(int x,int f) { fa[x]=f;dep[x]=dep[f]+1;siz[x]=1; for(int i=head[x];i;i=edge[i].next) { int u=edge[i].to; if(u==f)continue; dfs1(u,x);siz[x]+=siz[u]; if(siz[u]>siz[to[x]])to[x]=u; } } void dfs2(int x) { in[id[x]=++tim]=x; if(to[x])tp[to[x]]=tp[x],dfs2(to[x]); for(int i=head[x];i;i=edge[i].next) { int u=edge[i].to; if(u!=fa[x]&&u!=to[x])tp[u]=u,dfs2(u); } } data update(ull op,ull w) { data ret; if(op==1)ret.p0=(0&w),ret.p1=((~0)&w); if(op==2)ret.p0=(0|w),ret.p1=((~0)|w); if(op==3)ret.p0=(0^w),ret.p1=((~0)^w); return ret; } data pushup(data x,data y) { data ret; ret.p0=(x.p0&y.p1) | ((~x.p0)&y.p0); ret.p1=(x.p1&y.p1) | ((~x.p1)&y.p0); return ret; } void build(int x,int l,int r) { t[x].l=l;t[x].r=r; if(l==r) { tl[x]=tr[x]=update(op[in[l]][0],op[in[l]][1]);//in[l]而非x! return; } int mid=((l+r)>>1); build(x<<1,l,mid); build(x<<1|1,mid+1,r); tl[x]=pushup(tl[x<<1],tl[x<<1|1]); // tr[x]=pushup(tr[x<<1],tr[x<<1|1]); tr[x]=pushup(tr[x<<1|1],tr[x<<1]);//!!!!!!!!!! } data sch(int x,int l,int r,int fl) { if(t[x].l>=l&&t[x].r<=r) return fl?tr[x]:tl[x]; // int mid=((l+r)>>1); int mid=((t[x].l+t[x].r)>>1); if(r<=mid)return sch(x<<1,l,r,fl); else if(l>mid)return sch(x<<1|1,l,r,fl); else return pushup(sch((x<<1)+fl,l,r,fl),sch((x<<1|1)-fl,l,r,fl));//从左往右或从右往左pushup有不同 } data find(int x,int y) { data ans1=update(3,0),ans2=update(3,0);//ans1为x到lca，ans2为y到lca while(tp[x]!=tp[y]) { // if(dep[x]>dep[y]) if(dep[tp[x]]>dep[tp[y]]) { ans1=pushup(ans1,sch(1,id[tp[x]],id[x],1)); x=fa[tp[x]]; } else { ans2=pushup(sch(1,id[tp[y]],id[y],0),ans2); y=fa[tp[y]]; } } if(dep[x]<dep[y])return pushup(pushup(ans1,sch(1,id[x],id[y],0)),ans2); else return pushup(pushup(ans1,sch(1,id[y],id[x],1)),ans2); } void query(int x,int y,ull z)//ull { data ans=find(x,y);ull s=0,ret=0; for(int i=p-1;i>=0;i--) { if((1ull<<i)&ans.p0)ret+=(1ull<<i); else if(((1ull<<i)&ans.p1)&&s+(1ull<<i)<=z) ret+=(1ull<<i),s+=(1ull<<i); } printf("%llu ",ret); } void modify(int x,int p,ull op,ull w)//ull { if(t[x].l==t[x].r) { tl[x]=tr[x]=update(op,w); return;// } int mid=((t[x].l+t[x].r)>>1); if(p<=mid)modify(x<<1,p,op,w); else modify(x<<1|1,p,op,w); tl[x]=pushup(tl[x<<1],tl[x<<1|1]); // tr[x]=pushup(tr[x<<1],tr[x<<1|1]); tr[x]=pushup(tr[x<<1|1],tr[x<<1]); } int main() { scanf("%d%d%d",&n,&m,&p); for(int i=1;i<=n;i++)scanf("%llu%llu",&op[i][0],&op[i][1]); for(int i=1,x,y;i<n;i++)scanf("%d%d",&x,&y),add(x,y),add(y,x); dfs1(1,0);tp[1]=1;dfs2(1);build(1,1,n); for(int i=1,q,x,y;i<=m;i++) { ull z;// scanf("%d%d%d%llu",&q,&x,&y,&z); if(q==1)query(x,y,z); else modify(1,id[x],y,z);// } return 0; }