太痛苦了。。。

经过测试我 splay 中 rotate 操作连续调用了超过 114514 次（？貌似是有地方挂了，应该不是常数的问题/kk

求调求调/dk

#include<iostream>
#include<cstring>
#include<algorithm>
#include<cstdlib>
#include<cstdio>
#include<vector>
using namespace std;
int read(){
	int x=0;
	char ch=getchar();
	while(ch<'0'||ch>'9')ch=getchar();
	while(ch>='0'&&ch<='9'){
		x=(x<<1)+(x<<3)+(ch-'0');
		ch=getchar();
	} 
	return x;
} 
struct point{
	int s[3],fa=0,sz=0,val=0,sum=0;
	int col=0;
}pt[100050];
int n,m;
int get(int p){
	if(pt[pt[p].fa].s[0]==p)return 0;
	if(pt[pt[p].fa].s[1]==p)return 1;
	return 2;
}
void push_up(int p){
	if(p==0)return;
	pt[p].sz=pt[pt[p].s[0]].sz+pt[pt[p].s[1]].sz+1;
	pt[p].sum=pt[pt[p].s[0]].sum|pt[pt[p].s[1]].sum|pt[p].val;
}
void push_down(int p){
	if(pt[p].col){
		pt[pt[p].s[0]].col=pt[p].col;pt[pt[p].s[1]].col=pt[p].col;
		pt[pt[p].s[0]].val=pt[p].col;pt[pt[p].s[1]].val=pt[p].col;
		pt[p].col=0;
	}
}
void update(int p){
	if(get(p)!=2)update(pt[p].fa);
	push_down(p);
}
void rotate(int p){
	int fa=pt[p].fa,op=get(p);
	pt[pt[fa].fa].s[get(fa)]=p;pt[p].fa=pt[fa].fa;
	pt[fa].s[op]=pt[p].s[op^1];pt[pt[p].s[op^1]].fa=fa;
	pt[p].s[op^1]=fa;pt[fa].fa=p;
	push_up(fa);push_up(p);
}
void splay(int p){
	update(p);
	while(get(p)!=2&&get(pt[p].fa)!=2){
		if(get(p)==get(pt[p].fa))rotate(pt[p].fa),rotate(p);
		else rotate(p),rotate(p);
	}
	if(get(p)!=2)rotate(p);	
}
int access(int p){
	int rs=0;
	while(p!=0){
		splay(p);
		pt[p].s[1]=rs;
		push_up(p);
		rs=p;p=pt[p].fa;
	}
	return rs;
}
void link(int x,int y,int c){
	if(x==y)return;
	access(y);splay(y);splay(x);
	if(pt[y].fa!=0)return;
	pt[pt[x].s[0]].fa=pt[x].fa;
	push_up(pt[x].fa);
	pt[x].fa=y;pt[x].val=c;push_up(x);
}
void mdf(int x,int y,int c){
	
	if(x==y)return;
	int lca;access(y);lca=access(x);
	splay(y);splay(x);if(pt[y].fa==0)return;
	if(y==lca){
		splay(lca);
		pt[pt[lca].s[1]].col=c;
		return;
	}
	if(x==lca){
		splay(y);pt[y].col=c;return;
	}
	splay(lca);
	pt[pt[lca].s[1]].col=c;
	pt[y].col=c;
	return;
}
struct pr{
	int ls,rs;
};
pr query(int x,int y){
	if(x==y)return{0,0};
	int lca;access(y);lca=access(x);
	splay(y);splay(x);if(pt[y].fa==0)return {0,0};
	if(y==lca){
		splay(lca);
		return {pt[pt[lca].s[1]].sum,pt[pt[lca].s[1]].sz};
	}
	if(x==lca){
		splay(y);
		return {pt[y].sum,pt[y].sz};
	}
	splay(lca);
	return {pt[pt[lca].s[1]].sum|pt[y].sum,pt[pt[lca].s[1]].sz+pt[y].sz};
}
int pow(int p){
	return (1<<p);
}
int bitcount(int p){
	int ret=0;
	while(p){
		ret++;p=p&(p-1);
	}
	return ret;
}
int main(){
	n=read();m=read();
	for(int i=1;i<=n;i++){
		pt[i].fa=read();
	}
	for(int i=1;i<=n;i++){
		pt[i].val=pow(read());
		push_up(i);
	}
	for(int i=1;i<=m;i++){
		int op=read();
		if(op==1){
			int a=read(),b=read(),c=read();
			link(a,b,pow(c));
		}else if(op==2){
			int a=read(),b=read(),c=read();
			mdf(a,b,pow(c));
		}else if(op==3){
			int a=read(),b=read();
			pr ot=query(a,b);
			printf("%d %d\n",ot.rs,bitcount(ot.ls));
		}
	}
}