被sone1虐得意识模糊。

想看正文的直接跳到下一部分。

我为什么要学这个东西呢……?

故事是这样的:

蒟蒻rxd在学习WC洲爷的营员交流——LCM,

翻到最后发现有个参考文献,是某年某篇集训队论文。

然后点了进去,看到一个“sone1的ETT+LCT解法”,粗略一看觉得很厉害并且很优美啊……

但是仔细想了想不知道如何把ETT上一个点多次出现的信息维护在一个点上，于是去问洲爷。洲爷表示这个人是口胡的……并告诉我按照松爷的DFS序换根方法是能做的……

于是我去看了看松爷ZJOI上讲课的课件，感觉似乎有点道理……但是有些细节搞不太清楚……就又去咨询松爷T_T。

然后骚扰了松爷好长时间，最后得出结论这个方法太麻烦了QAQ……(其实是我太弱啦……

然后觉得sone1既然已经开了，花了一天的时间了，不A了难受……就去学了下Toptree。

然后就又搭了好多天时间进去……

什么是Toptree呢……?

​就是某大爷NOI考场上用来和树剖对拍的东西。

它可以支持子树操作、链操作、换根、砍树等。

考虑LCT在维护重链信息的同时顺便维护轻儿子的信息，在每个点上用一个数据结构维护这个东西，在轻重边交替的时候在这个数据结构里插入/删除。

（我不会证）由于轻重边变换次数是均摊O(log n)的,如果用Splay维护轻儿子的信息据说复杂度还是一个log……?

听起来很容易啊……具体怎么写呢……?

那个辅助的数据结构需要满足这些性质:能够插入、删除任意值，同时维护标记。

平衡树(Splay,Treap)显然是可行的。至于一部分大爷写的可并堆……斜堆和左偏树的树高可以卡到O(n)，没法在删除任意值的情况下维护标记……随机合并的堆(即Merge(A,B)时随机交换A,B)期望树高是n/2的……?感觉都不是很靠谱。我为了搞笑就写了个Treap，也不知道复杂度会不会因此退化。不产生歧义，下文的“Treap”就是指代“维护轻儿子的数据结构”。

我们需要明确下面几个东西:

TopTree上的Cover/Plus:把Splay的子树表示的那一条重链赋值/加。

TopTree上的CoverTree/PlusTree:把Splay的子树表示的那一条重链上的所有点连出去的轻儿子对应的子树赋值/加。不包括这条重链。注意是子树赋值/加，因此包括了轻儿子的链及那条链上的轻儿子……

Treap上的Cover/Plus:把这棵Treap表示的那一坨轻儿子（其实表示的是一些子树）赋值/加。

要注意x->CoverTree()和x->treap->Cover()的区别!……（好显然啊，但是我一开始写就是搞错了TAT。

然后就没什么了啊……实现上面有一些技巧。

（网上的一些题解说的加入内部节点是什么意思呢……并没有看懂……可能因为我写的不是Splay……?

在CoverTree的时候需要在Treap根部那个点维护一下，然而Treap上面的点Cover时需要在对应的Splay上的点Cover并CoverTree……这不是无解的环么……

我们可以在Treap根部加入一个空节点，并保证不管怎么删除/插入，这个节点始终在根部——把它的fix设成-1即可。

没啥了。大力调吧。

#include<cstdio>
#include<cctype>
#include<cstring>
#include<algorithm>

#define For(i,x,y) for (int i=x;i<y;i++)
#define mp make_pair
#define fir first
#define sec second
using namespace std;

typedef long long LL;
typedef double Db;

const int N=200000+19,oo=(1<<30)-1,Len=8000000;
struct Edge {int y,nxt;} E[N*2];
int Last[N],n,Qc,opt,x,y,z,cnt;
char Buf[Len],*b=Buf+Len;
struct node;

inline int ch()
{
	if (b==Buf+Len) fread(Buf,1,Len,stdin),b=Buf;
	return *b++;
}
int IN()
{
	int c,f,x;
	while (!isdigit(c=ch())&&c!='-');c=='-'?(f=1,x=0):(f=0,x=c-'0');
	while (isdigit(c=ch())) x=(x<<1)+(x<<3)+c-'0';return !f?x:-x;
}
void Print(int x)
{
	if (x>=10) Print(x/10);
	putchar(x%10+'0');
}

struct Treap *nul;
struct Treap
{
	Treap *L,*R;
	node *x;
	int fix,key,S;
	int Set,Add;
	int __Size,__Min,__Max,__Sum;
	int Size,Min,Max,Sum;

	void Update()
	{
		if (this==nul) return;
		S=L->S+R->S+1;
		Size=L->Size+R->Size+__Size;
		Min=min(min(L->Min,R->Min),__Min);
		Max=max(max(L->Max,R->Max),__Max);
		Sum=L->Sum+R->Sum+__Sum;
	}
	void Reset(int Sz,int Mn,int Mx,int Sm)
	{
		__Size=Sz,__Min=Mn,__Max=Mx,__Sum=Sm;
		Update();
	}
	void Cover(int v)
	{
		if (this==nul||!Size) return;
		Set=v,Add=0;
		if (__Size) __Min=__Max=v,__Sum=v*__Size;
		Min=Max=v;
		Sum=v*Size;
	}
	void Plus(int v)
	{
		if (this==nul||!Size) return;
		if (Set) Set+=v;else Add+=v;
		if (__Size) __Min+=v,__Max+=v,__Sum+=v*__Size;
		Min+=v,Max+=v;
		Sum+=v*Size;
	}
	void Down();
} Tnd[2*N],*cur=Tnd+1;
typedef pair<Treap*,Treap*> Ptt;

Treap *TNew(int pos,int v)
{
	Treap *x=cur++;
	x->L=x->R=nul;
	x->fix=~v?rand():-1;
	x->key=pos;
	x->Set=-1,x->Add=0;
	if (~v) x->__Size=1,x->__Min=x->__Max=x->__Sum=v;
		else x->__Size=0,x->__Min=oo,x->__Max=-oo,x->__Sum=0;
	return x->Update(),x;
}
Treap *Merge(Treap *A,Treap *B)
{
	if (A==nul) return B;
	if (B==nul) return A;
	A->Down(),B->Down();
	if (A->fix<B->fix) return A->R=Merge(A->R,B),A->Update(),A;
		else return B->L=Merge(A,B->L),B->Update(),B;
}
Ptt Split(Treap *A,int k)
{
	if (A==nul) return mp(nul,nul);
	Ptt Ans;A->Down();
	if (k<=A->L->S) Ans=Split(A->L,k),A->L=Ans.sec,A->Update(),Ans.sec=A;
		else Ans=Split(A->R,k-A->L->S-1),A->R=Ans.fir,A->Update(),Ans.fir=A;
	return Ans;
}
int Rank(Treap *x,int v)
{
	if (x==nul) return 0;
	x->Down();
	return v<x->key?Rank(x->L,v):Rank(x->R,v)+x->L->S+1;
}
void Ins(Treap *&x,Treap *y)
{
	Ptt A;
	A=Split(x,Rank(x,y->key));
	x=Merge(Merge(A.fir,y),A.sec);
}
void Del(Treap *&x,Treap *y)
{
	Ptt A,B;
	A=Split(x,Rank(x,y->key)-1);
	B=Split(A.sec,1);
	x=Merge(A.fir,B.sec);
}

struct node *null;
struct node
{
	node *L,*R,*Fa;
	Treap *t,*x;
	int rev,Add,Set,AddT,SetT;
	int key;
	int Size,Sum,Min,Max,SizeT,SumT,MinT,MaxT;
	
	void Reset()
	{
		x->Reset(Size+SizeT,min(Min,MinT),max(Max,MaxT),Sum+SumT);
	}
	bool Top(node *Aim)
	{
		return Aim==null?Fa==null||Fa->L!=this&&Fa->R!=this:Fa==Aim;
	}
	void Update()
	{
		if (this==null) return;
		Size=L->Size+R->Size+1;
		Sum=L->Sum+R->Sum+key;
		Min=min(min(L->Min,R->Min),key);
		Max=max(max(L->Max,R->Max),key);

		SizeT=L->SizeT+R->SizeT+t->Size;
		SumT=L->SumT+R->SumT+t->Sum;
		MinT=min(min(L->MinT,R->MinT),t->Min);
		MaxT=max(max(L->MaxT,R->MaxT),t->Max);
	}
	void Reverse() {rev^=1,swap(L,R);}
	void Cover(int v)
	{
		if (this==null) return;
		Set=v,Add=0;
		Sum=v*Size;
		Min=Max=key=v;
	}
	void Plus(int v)
	{
		if (this==null) return;
		if (Set) Set+=v;else Add+=v;
		Sum+=v*Size;
		Min+=v,Max+=v,key+=v;
	}
	void CoverTree(int v)
	{
		if (this==null||!SizeT) return;
		SetT=v,AddT=0;
		t->Cover(v);
		MinT=MaxT=v;
		SumT=SizeT*v;
	}
	void PlusTree(int v)
	{
		if (this==null||!SizeT) return;
		if (SetT) SetT+=v;else AddT+=v;
		t->Plus(v);
		MinT+=v,MaxT+=v;
		SumT+=SizeT*v;
	}
	void Down()
	{
		if (this==null) return;
		if (rev) L->Reverse(),R->Reverse(),rev=0;
		if (Set) L->Cover(Set),R->Cover(Set),Set=0;
		if (Add) L->Plus(Add),R->Plus(Add),Add=0;
		if (SetT) L->CoverTree(SetT),R->CoverTree(SetT),SetT=0;
		if (AddT) L->PlusTree(AddT),R->PlusTree(AddT),AddT=0;
	}
	void Zig()
	{
		node *y=Fa,*z=y->Fa;
		if (y==z->L) z->L=this;else if (y==z->R) z->R=this;Fa=z;
		y->L=R;if (R!=null) R->Fa=y;
		R=y,y->Fa=this;y->Update();
	}
	void Zag()
	{
		node *y=Fa,*z=y->Fa;
		if (y==z->L) z->L=this;else if (y==z->R) z->R=this;Fa=z;
		y->R=L;if (L!=null) L->Fa=y;
		L=y,y->Fa=this;y->Update();
	}
} Nd[N];

void Splay(node *x,node *Aim=null)
{
	static node *S[N];node *tmp=x;int k=0;
	while (!tmp->Top(Aim)) S[++k]=tmp,tmp=tmp->Fa;S[++k]=tmp;
	while (k) S[k--]->Down();
	while (!x->Top(Aim))
	{
		node *y=x->Fa,*z=y->Fa;
		if (!y->Top(Aim))
			if (x==y->L) if (y==z->L) y->Zig(),x->Zig();else x->Zig(),x->Zag();
				else if (y==z->L) x->Zag(),x->Zig();else y->Zag(),x->Zag();
		else if (x==y->L) x->Zig();else x->Zag();
	}
	x->Update();
}
node *Left(node *x)
{
	x->Down();
	while (x->L!=null) x=x->L,x->Down();
	return x;
}
node *Right(node *x)
{
	x->Down();
	while (x->R!=null) x=x->R,x->Down();
	return x;
}
node *Father(node *x) {while (!x->Top(null)) x=x->Fa;return x;}
node *Access(node *x)
{
	node *y;
	for (y=null;x!=null;y=x,x=x->Fa)
	{
		Splay(x);
		if (y!=null) Del(x->t,Left(y)->x);
		node *z=Left(x->R);
		if (z!=null) Splay(z,x),z->Reset(),Ins(x->t,z->x);
		x->R=y,x->Update();
	}
	return y;
}

void Treap::Down()
{
	if (this==nul) return;
	if (Set)
	{
		L->Cover(Set),R->Cover(Set);
		node *u=Father(L->x),*v=Father(R->x);
		u->Cover(Set),u->CoverTree(Set);
		v->Cover(Set),v->CoverTree(Set);
		Set=0;
	}
	if (Add)
	{
		L->Plus(Add),R->Plus(Add);
		node *u=Father(L->x),*v=Father(R->x);
		u->Plus(Add),u->PlusTree(Add);
		v->Plus(Add),v->PlusTree(Add);
		Add=0;
	}
}

void QueryTree(node *x)
{
	int Ans;
	Access(x),Splay(x);
	if (opt==3) Ans=min(x->t->Min,x->key);
	if (opt==4) Ans=max(x->t->Max,x->key);
	if (opt==11) Ans=x->t->Sum+x->key;
	Print(Ans),puts("");
}
void ModifyTree(node *x,int v)
{
	Access(x),Splay(x);
	if (opt==0) x->t->Cover(v),x->key=v;
	if (opt==5) x->t->Plus(v),x->key+=v;
	x->Update();
}
void Evert(node *x) {Access(x)->Reverse();}
void QueryChain(node *x,node *y)
{
	node *z;int Ans;
	Access(x),z=Access(y);
	Ans=z->key,z=z->R;
	if (opt==7) Ans=min(Ans,z->Min);
	if (opt==8) Ans=max(Ans,z->Max);
	if (opt==10) Ans=Ans+z->Sum;
	z=Access(x)->R;
	if (opt==7) Ans=min(Ans,z->Min);
	if (opt==8) Ans=max(Ans,z->Max);
	if (opt==10) Ans=Ans+z->Sum;
	Print(Ans),puts("");
}
void ModifyChain(node *x,node *y,int v)
{
	node *z;
	Access(x),z=Access(y);
	if (opt==2) z->key=v,z->R->Cover(v);else z->key+=v,z->R->Plus(v);
	z->Update();
	z=Access(x);
	if (opt==2) z->R->Cover(v);else z->R->Plus(v);
	z->Update();
}
void Change(node *x,node *y)
{
	Access(y),Splay(x);
	if (Father(y)==x) return;
	Access(x),Splay(x);
	x->L->Fa=null;
	x->L=null,x->Update();
	x->Reset();
	Access(y),Splay(y),x->Fa=y,y->R=x,y->Update();
}

void New(int pos,int v)
{
	node *x=Nd+pos;
	x->L=x->R=x->Fa=null;
	x->Set=x->SetT=-1;
	x->t=TNew(0,-1);
	x->x=TNew(pos,v);
	x->t->x=x->x->x=x;
	x->key=v;
	x->Update();
}
void Init()
{
	null=Nd;nul=Tnd;
	
	null->L=null->R=null->Fa=null;
	null->t=null->x=nul;
	null->Min=null->MinT=oo;
	null->Max=null->MaxT=-oo;
	nul->L=nul->R=nul;
	nul->x=null;
	nul->Min=oo;
	nul->Max=-oo;
	
	For(i,1,n+1) New(i,IN());
}
void DFS(node *x)
{
	for (int i=Last[x-Nd],y;~i;i=E[i].nxt)
		if ((y=E[i].y)!=x->Fa-Nd)
		{
			node *d=Nd+y;
			d->Fa=x;
			DFS(d);
			Ins(x->t,d->x);
		}
	x->x->Reset(x->t->Size+1,min(x->key,x->t->Min),max(x->key,x->t->Max),x->key+x->t->Sum);
	x->Update();
}
void Link(int x,int y)
{
	E[cnt]=(Edge){y,Last[x]};Last[x]=cnt++;
	E[cnt]=(Edge){x,Last[y]};Last[y]=cnt++;
}

int main()
{
	freopen("3153.in","r",stdin);
	freopen("3153.out","w",stdout);
	memset(Last,-1,sizeof(Last));
	n=IN(),Qc=IN();
	For(i,1,n) Link(IN(),IN());
	Init();
	DFS(Nd+IN());
	while (Qc--)
	{
		opt=IN();
		if (opt==0||opt==5) x=IN(),y=IN(),ModifyTree(Nd+x,y);
		if (opt==1) Evert(Nd+IN());
		if (opt==2||opt==6) x=IN(),y=IN(),z=IN(),ModifyChain(Nd+x,Nd+y,z);
		if (opt==3||opt==4||opt==11) QueryTree(Nd+IN());
		if (opt==7||opt==8||opt==10) QueryChain(Nd+IN(),Nd+IN());
		if (opt==9) x=IN(),y=IN(),Change(Nd+x,Nd+y);
	}
}