30分 WA 求调 玄关

#include<bits/stdc++.h>
#define ls (rt<<1)
#define rs (rt<<1|1)
#define mid ((l+r)>>1)
#define lson ls,l,mid
#define rson rs,mid+1,r
#define int unsigned long long
using namespace std;
using ll = unsigned long long;
const int N = 2e5+5;
const ll LIM = 0-1;
int n,m,k,dep[N],son[N],tp[N],tim,dfn[N],pos[N],fa[N],siz[N],cnt1,cnt2;
vector<int> e[N];
struct node{
    ll opt,x;
    ll ask(ll y){
        if(opt==1) return y&x;
        if(opt==2) return y|x;
        if(opt==3) return y^x;
    }
}a[N];
void dfs1(int x){
    dep[x]=dep[fa[x]]+1;siz[x]=1;
    for(int i : e[x]){
        if(i==fa[x]) continue;
        fa[i]=x;dfs1(i);siz[x]+=siz[i];
        if(siz[i]>siz[son[x]]) son[x]=i;
    }
}void dfs2(int x,int top){
    tp[x]=top;dfn[x]=++tim;pos[tim]=x;if(son[x]) dfs2(son[x],top);
    for(int i : e[x]){
        if(i==fa[x]||i==son[x]) continue;
        dfs2(i,i);
    }
}struct nod{
    ll ans1[2],ans2[2];
};nod operator+ (nod a,nod b){
    nod nodd;
    nodd.ans1[1]=(a.ans1[1]&b.ans1[1])|((~a.ans1[1])&b.ans1[0]);
    nodd.ans1[0]=(a.ans1[0]&b.ans1[1])|((~a.ans1[0])&b.ans1[0]);
    nodd.ans2[1]=(a.ans2[1]&b.ans2[1])|((~a.ans2[1])&b.ans2[0]);
    nodd.ans2[0]=(a.ans2[0]&b.ans2[1])|((~a.ans2[0])&b.ans2[0]);
    return nodd;
}nod ans1[N],ans2[N];
struct Seg{
    nod t[N<<2];
    void build(int rt,int l,int r){
        if(l==r){
            t[rt].ans1[0]=t[rt].ans2[0]=a[pos[l]].ask(0);
            t[rt].ans1[1]=t[rt].ans2[1]=a[pos[l]].ask(LIM);
            return;
        }build(lson);build(rson);
        t[rt]=t[ls]+t[rs];
    }void modify(int rt,int l,int r,int p,int op,ll k){
        if(l==r&&l==p){
            a[l].opt=op;a[l].x=k;
            t[rt].ans1[0]=t[rt].ans2[0]=a[pos[l]].ask(0);
            t[rt].ans1[1]=t[rt].ans2[1]=a[pos[l]].ask(LIM);
            return;
        }if(p<=mid) modify(lson,p,op,k);
        else modify(rson,p,op,k);
        t[rt]=t[ls]+t[rs];
    }nod query(int rt,int l,int r,int ll,int rr){
        if(ll<=l&&rr>=r) return t[rt];
        if(ll<=mid){
            if(rr>mid) return query(lson,ll,rr)+query(rson,ll,rr);
            else return query(lson,ll,rr);
        }else return query(rson,ll,rr);
    }
}Tr;
nod solve(int x,int y){
    cnt1=cnt2=0;
    while(tp[x]!=tp[y]){
        if(dep[tp[x]]>dep[tp[y]]){
            ans1[++cnt1]=Tr.query(1,1,n,dfn[tp[x]],dfn[x]);
            x=fa[tp[x]];
        }else{
            ans2[++cnt2]=Tr.query(1,1,n,dfn[tp[y]],dfn[y]);
            y=fa[tp[y]];
        }
    }if(dep[x]>dep[y]) ans1[++cnt1]=Tr.query(1,1,n,dfn[y],dfn[x]);
    else ans2[++cnt2]=Tr.query(1,1,n,dfn[x],dfn[y]);
    nod re;for(int i=1;i<=cnt1;i++){
        swap(ans1[i].ans1[1],ans1[i].ans2[1]);
        swap(ans1[i].ans1[0],ans1[i].ans2[0]);
    }if(cnt1){
        re=ans1[1];
        for(int i=2;i<=cnt1;i++) re=re+ans1[i];
        if(cnt2) re=re+ans2[cnt2];
    }else re=ans2[cnt2];
    for(int i=cnt2;i>=1;i--) re=re+ans2[i];
    return re;
}signed main(){
    ios::sync_with_stdio(0);cin.tie(0);cout.tie(0);
    cin>>n>>m>>k;
    for(int i=1;i<=n;i++) cin>>a[i].opt>>a[i].x;
    for(int i=1,u,v;i<n;i++){
        cin>>u>>v;
        e[u].push_back(v);
        e[v].push_back(u);
    }dfs1(1);dfs2(1,1);Tr.build(1,1,n);
    for(int i=1,q,x,y,z;i<=m;i++){
        cin>>q>>x>>y>>z;
        if(q==2){
            Tr.modify(1,1,n,dfn[x],y,z);
        }else{
            nod re=solve(x,y);ll zer=re.ans1[0],one=re.ans1[1],ans=0;
            for(signed i=63;i>=0;i--){
                ll tmp0=(zer>>i)&1ull;
                ll tmp1=(one>>i)&1ull;
                if(tmp0>=tmp1||(1ull<<i)>z) ans|=(tmp0?(1ull<<i):0);
                else ans|=(tmp1?(1ull<<i):0),z-=(1ull<<i);
            }cout<<ans<<"\n";
        }
    }return 0;
}