实现细节较多,详见代码
#include<cstdio>
#include<iostream>
#include<cstring>
#include<algorithm>
#define debug(...) fprintf(stderr,__VA_ARGS__)
#define Debug(x) cout<<#x<<"="<<x<<endl
using namespace std;
typedef unsigned long long LL;//64为,要开ull
const LL INF=0-1;
inline LL read(){
register LL x=0;register char c=getchar();
while(c<48||c>57){c=getchar();}
while(c>=48&&c<=57)x=(x<<3)+(x<<1)+(c&15),c=getchar();
return x;
}
const int MAXN=200005;
const int MAXM=400005;
struct Edge{
int v,next;
}e[MAXM];
int first[MAXN],Ecnt=1;
inline void Add_edge(int u,int v){
e[++Ecnt]=(Edge){v,first[u]};
first[u]=Ecnt;
}
int fa[MAXN],son[MAXN],size[MAXN],dep[MAXN],seg[MAXN],rev[MAXN],top[MAXN];
int n,m,K;
LL ans;
inline void dfs1(int u,int pre){
dep[u]=dep[pre]+1,size[u]=1,fa[u]=pre;
for(int i=first[u];i;i=e[i].next){
int v=e[i].v;
if(v==pre) continue;
dfs1(v,u);
size[u]+=size[v];
if(size[v]>size[son[u]]) son[u]=v;
}
}
inline void dfs2(int u,int pre){
seg[u]=++seg[0];
rev[seg[0]]=u;
if(son[u]){
top[son[u]]=top[u];
dfs2(son[u],u);
}
for(int i=first[u];i;i=e[i].next){
int v=e[i].v;
if(v==pre||v==son[u]) continue;//记得判重儿子不能再走
top[v]=v;
dfs2(v,u);
}
}
namespace SGT{
struct data{
LL f0,f1,inv0,inv1;
data(){f0=f1=inv0=inv1=0;}
}a[MAXN<<2],ans1[MAXN],ans2[MAXN];
LL val[MAXN];int op[MAXN];
int cnt1,cnt2;
#define ls (rt<<1)
#define rs (rt<<1|1)
inline LL calc(LL num,int x){
if(op[x]==1) return num&val[x];
if(op[x]==2) return num|val[x];
if(op[x]==3) return num^val[x];
}
inline data update(data l,data r){
data res;
res.f0=((l.f0&r.f1)|((~l.f0)&r.f0));//想清楚
res.f1=((l.f1&r.f1)|((~l.f1)&r.f0));
res.inv0=((r.inv0&l.inv1)|((~r.inv0)&l.inv0));
res.inv1=((r.inv1&l.inv1)|((~r.inv1)&l.inv0));
return res;
}
inline void pushup(int rt){
a[rt]=update(a[ls],a[rs]);
}
inline void build(int rt,int l,int r){
if(l==r){
a[rt].f0=a[rt].inv0=calc(0,rev[l]);
a[rt].f1=a[rt].inv1=calc(INF,rev[l]);
return;
}
int mid=(l+r)>>1;
build(ls,l,mid);
build(rs,mid+1,r);
pushup(rt);
}
inline void modify(int rt,int l,int r,int pos){
if(l==r){
a[rt].f0=a[rt].inv0=calc(0,rev[l]);
a[rt].f1=a[rt].inv1=calc(INF,rev[l]);
return;
}
int mid=(l+r)>>1;
if(pos<=mid) modify(ls,l,mid,pos);
else modify(rs,mid+1,r,pos);
pushup(rt);
}
inline data query(int rt,int l,int r,int x,int y){
if(l>=x&&r<=y) return a[rt];
int mid=(l+r)>>1;
if(y<=mid) return query(ls,l,mid,x,y);
if(x>mid) return query(rs,mid+1,r,x,y);
return update(query(ls,l,mid,x,y),query(rs,mid+1,r,x,y));
}
inline data solve(int x,int y){
cnt1=cnt2=0;
while(top[x]!=top[y]){
if(dep[top[x]]>=dep[top[y]]){
ans1[++cnt1]=query(1,1,n,seg[top[x]],seg[x]);
x=fa[top[x]];
}
else{
ans2[++cnt2]=query(1,1,n,seg[top[y]],seg[y]);
y=fa[top[y]];
}
}
if(dep[x]>dep[y]) ans1[++cnt1]=query(1,1,n,seg[y],seg[x]);
else ans2[++cnt2]=query(1,1,n,seg[x],seg[y]);
data res;
for(int i=1;i<=cnt1;i++) swap(ans1[i].f0,ans1[i].inv0),swap(ans1[i].f1,ans1[i].inv1);//选一个方向反过来
if(cnt1){
res=ans1[1];
for(int i=2;i<=cnt1;i++) res=update(res,ans1[i]);
if(cnt2) res=update(res,ans2[cnt2]);
}
else res=ans2[cnt2];
for(int i=cnt2-1;i>=1;i--) res=update(res,ans2[i]);
return res;
}
#undef ls
#undef rs
}using namespace SGT;
signed main(){
//freopen("asd.in","r",stdin);
n=read(),m=read(),K=read();
for(int i=1;i<=n;i++) op[i]=read(),val[i]=read();
for(int i=1;i<=n-1;i++){
int x=read(),y=read();
Add_edge(x,y);
Add_edge(y,x);
}
dfs1(1,0);
top[1]=1;dfs2(1,0);
build(1,1,n);
while(m--){
int opt=read(),x=read(),y=read();LL z=read();
if(opt==1){
data res=solve(x,y);ans=0;//把64的状态存到一个unsigned long long里面,优化掉k
for(int i=63;i>=0;i--){
LL tmp0=(res.f0>>i)&(1ull);
LL tmp1=(res.f1>>i)&(1ull);
if(tmp0>=tmp1||(1ull<<i)>z) ans|=(tmp0?(1ull<<i):0);//贪心，也要想清楚
else ans|=tmp1?(1ull<<i):0,z-=(1ull<<i);//所选数不能超过z
}
printf("%llu\n",ans);
}
if(opt==2){
op[x]=y,val[x]=z;
modify(1,1,n,seg[x]);
}
}
}