题目：
解题思路：
LCT，主要是维护链上的多位贪心答案，推个公式：分类讨论入0/1的情况，合并就好了（公式是合并用的）
代码（我不知道之前那个为啥一直wa，改成结构体就好了QAQ：
#include<cstdio>
#include<cstring>
#include<algorithm>
#define lll tr[spc].ch[0]
#define rrr tr[spc].ch[1]
#define lls tr[spc].dt[0]
#define rrs tr[spc].dt[1]
#define ls ch[0]
#define rs ch[1]
#define ll dt[0]
#define rr dt[1]
#define aa (unsigned long long)(0ull)
#define bb (unsigned long long)(~(ul)(0ull))
typedef unsigned long long ul;
using std::swap;
struct data{
ul v0;
ul v1;
data friend operator + (data x,data y)
{
data ans;
ans.v0=(~x.v0&y.v0)|(x.v0&y.v1);
ans.v1=(~x.v1&y.v0)|(x.v1&y.v1);
return ans;
}
};
struct trnt{
int ch[];
int fa;
int lzt;
data val;
data dt[];
bool anc;
}tr[];
int n,m,k;
ul qcc[];
bool whc(int spc)
{
return tr[tr[spc].fa].rs==spc;
}
void pushup(int spc)
{
lls=rrs=tr[spc].val;
if(lll)
{
lls=tr[lll].ll+lls;
rrs=rrs+tr[lll].rr;
}
if(rrr)
{
lls=lls+tr[rrr].ll;
rrs=tr[rrr].rr+rrs;
}
return ;
}
void trr(int spc)
{
if(!spc)
return ;
swap(lll,rrr);
swap(lls,rrs);
tr[spc].lzt^=;
return ;
}
void pushdown(int spc)
{
if(tr[spc].lzt)
{
tr[spc].lzt=;
trr(lll);
trr(rrr);
}
return ;
}
void recal(int spc)
{
if(!tr[spc].anc)
recal(tr[spc].fa);
pushdown(spc);
return ;
}
void rotate(int spc)
{
int f=tr[spc].fa;
bool k=whc(spc);
tr[f].ch[k]=tr[spc].ch[!k];
tr[spc].ch[!k]=f;
if(tr[f].anc)
{
tr[spc].anc=;
tr[f].anc=;
}else
tr[tr[f].fa].ch[whc(f)]=spc;
tr[spc].fa=tr[f].fa;
tr[f].fa=spc;
tr[tr[f].ch[k]].fa=f;
pushup(f);
pushup(spc);
return ;
return ;
}
void splay(int spc)
{
recal(spc);
while(!tr[spc].anc)
{
int f=tr[spc].fa;
if(tr[f].anc)
{
rotate(spc);
return ;
}
if(whc(spc)^whc(f))
rotate(spc);
else
rotate(f);
rotate(spc);
}
return ;
}
void access(int spc)
{
int lst=;
while(spc)
{
splay(spc);
tr[rrr].anc=;
tr[lst].anc=;
rrr=lst;
pushup(spc);
lst=spc;
spc=tr[spc].fa;
}
}
void Mtr(int spc)
{
access(spc);
splay(spc);
trr(spc);
return ;
}
void split(int x,int y)
{
Mtr(x);
access(y);
splay(y);
return ;
}
void link(int x,int y)
{
Mtr(x);
tr[x].fa=y;
return ;
}
ul vl(ul a,ul b,int op)
{
if(op==)
return a&b;
if(op==)
return a|b;
return a^b;
}
int main()
{
scanf("%d%d%d",&n,&m,&k);
qcc[]=;
for(int i=;i<=k;i++)
qcc[i]=qcc[i-]<<;
ul tmp=qcc[k]-;
for(int i=;i<=n;i++)
{
int opt;
scanf("%d",&opt);
ul x;
scanf("%llu",&x);
tr[i].anc=;
int spc=i;
lls.v0=rrs.v0=tr[i].val.v0=vl(,x,opt);
lls.v1=rrs.v1=tr[i].val.v1=vl(tmp,x,opt);
}
for(int i=;i<n;i++)
{
int a,b;
scanf("%d%d",&a,&b);
link(a,b);
}
while(m--)
{
int cmd;
scanf("%d",&cmd);
if(cmd==)
{
int x,y;
scanf("%d%d",&x,&y);
split(x,y);
ul z;
scanf("%llu",&z);
ul ans=;
ul tmp0=tr[y].ll.v0;
ul tmp1=tr[y].ll.v1;
for(int i=k-;i>=;i--)
{
if(qcc[i]&tmp0)
ans|=qcc[i];
else if((qcc[i]&tmp1)&&z>=qcc[i])
{
z-=qcc[i];
ans|=qcc[i];
}
}
printf("%llu\n",ans);
}else{
int x,y;
scanf("%d%d",&x,&y);
ul z;
scanf("%llu",&z);
splay(x);
tr[x].val.v0=vl(z,,y);
tr[x].val.v1=vl(z,tmp,y);
pushup(x);
}
}
return ;
}