C++11(clang++ 3.9) 解法, 执行用时: 2083ms, 内存消耗: 120280K, 提交时间: 2020-03-26 11:15:45

#include<iostream>
#include<cstdio>
#define ul unsigned long long
using namespace std;
int n,m,top,st[1001010];
int fa[1001010],s[1001011][2],rev[1001010];
char S[10];
struct ev
{
	ul f0,f1,val;
	int opt;
	ev operator + (const ev &b)const
	{
		ev res;
		res.f0=(~f0&b.f0)|(f0&b.f1);
		res.f1=(~f1&b.f0)|(f1&b.f1);
		res.val=val;
		res.opt=opt;
		return res;
	}
}v[1001010],anl[1001010],anr[1001010];
bool isrot(int x)
{
	return s[fa[x]][0]==x||s[fa[x]][1]==x;
}
void rv(int x)
{
	swap(s[x][0],s[x][1]);
	swap(anl[x],anr[x]);
	rev[x]^=1;
}
ev cg(ul vv,int op)
{
	if(op==1) return (ev){0,vv};
	if(op==2) return (ev){vv,0xffffffffffffffff};
	return (ev){vv,~vv};
}
void pushup(int x)
{
	int l=s[x][0],r=s[x][1];
	anl[x]=anr[x]=v[x];
	if(l)
	{
		if(!v[x].opt) anl[x]=cg(v[x].val,anr[l].opt)+anl[x];
		else anr[x]=anr[x]+cg(anr[l].val,v[x].opt);
		anl[x]=anl[l]+anl[x];
		anr[x]=anr[x]+anr[l]; 
	}
	if(r)
	{
		if(!v[x].opt) anr[x]=cg(v[x].val,anl[r].opt)+anr[x];
		else anl[x]=anl[x]+cg(anl[r].val,v[x].opt);
		anl[x]=anl[x]+anl[r];
		anr[x]=anr[r]+anr[x];
	}
}
void pushdown(int x)
{
	if(rev[x])
	{
		if(s[x][0]) rv(s[x][0]);
		if(s[x][1]) rv(s[x][1]);
		rev[x]=0;
	}
}
void rot(int x)
{
	int y=fa[x],z=fa[y],d=s[y][1]==x;
	if(isrot(y))
	s[z][s[z][1]==y]=x;
	fa[x]=z;
	fa[y]=x;
	if(s[x][!d])
	fa[s[x][!d]]=y;
	s[y][d]=s[x][!d];
	s[x][!d]=y;
	pushup(y);
}
void splay(int x)
{
	st[top=1]=x;
	for(int i=x;isrot(i);i=fa[i])
	st[++top]=fa[i];
	while(top)
	pushdown(st[top--]);
	while(isrot(x))
	{
		int y=fa[x],z=fa[y];
		if(isrot(y))
		(s[z][1]==y)^(s[y][1]==x)?rot(x):rot(y);
		rot(x); 
	}
	pushup(x);
}
void access(int x)
{
	for(int y=0;x;x=fa[y=x]) splay(x),s[x][1]=y,pushup(x);
}
void makeroot(int x)
{
	access(x);
	splay(x);
	rv(x);
}
void split(int x,int y)
{
	makeroot(x);
	access(y);
	splay(y);
}
void link(int x,int y,int z)
{
	makeroot(x);
	fa[x]=z;
	fa[z]=y;
}
int main()
{
	scanf("%d%d",&n,&m);
	for(int i=1;i<=n;i++)
	v[i].opt=2,v[i].f0=0,v[i].f1=0xffffffffffffffff,v[i].val=0;
	for(int i=n+1,x,y;i<=n+n-1;i++)
	{
		scanf("%d%d",&x,&y);
		link(x,y,i);
		v[i].opt=0;
		v[i].f0=0;
		v[i].f1=0xffffffffffffffff;
		v[i].val=0;
	}
	for(int i=1,t,x,y;i<=m;i++)
	{
		scanf("%d",&t);
		if(t==1)
		{
			ul z,k;
			scanf("%d%d%llu%llu",&x,&y,&z,&k);
			split(x,y);
			ev a1=anl[y]+cg(k,anr[y].opt);
			ul aa=a1.f0,bb=a1.f1,ans=0,t=1;
			for(int j=63;~j;j--)
			if((aa&(t<<j))==0&&(bb&(t<<j))&&(t<<j)<=z)
			ans+=(t<<j),z-=(t<<j);
			printf("%llu\n",ans); 
		}
		else if(t==2)
		{
			scanf("%d%s",&x,S);
			makeroot(x);
			if(S[0]=='a') v[x].opt=1;
			if(S[0]=='o') v[x].opt=2;
			if(S[0]=='x') v[x].opt=3;
			pushup(x);
		}
		else if(t==3)
		{
			ul z;
			scanf("%d%llu",&x,&z);
			makeroot(x+n);
			v[x+n].val=z;
			pushup(x+n);
		}
	}
	return 0;
}