Title Link

• Given a rootless tree with \ (n \) points, define its deletion sequence: delete the leaf node with the smallest number in the tree and add it to the end of the sequence each time.
• There are \ (q \) operations, which are divided into three types: set the number of a node to the maximum number of other nodes \ (+ 1 \); Query the position of a node in the deletion sequence; Ask the order of two nodes in the deletion sequence.
• \(1\le n,q\le2\times10^5\)

Nature of deletion sequence

Obviously, the maximum point must be at the end of the deletion sequence. Because unless there is only the last point, there must be more than one leaf node, and there must be a leaf node with a smaller number than the maximum point.

Then consider the second largest point and find out the tree path between it and the largest point. Then the points on this path must appear at the end of the deletion sequence from the second largest point. Similarly, unless the leaf node is exactly the second largest point and the largest point, there must be a leaf node with a smaller number than the second largest point; After deleting the second largest point, all points on the remaining path will be deleted in turn.

By analogy, consider each point from large to small. If it has not been determined, its path to the previously determined part will appear just in front of the previously determined part and at the end of the undetermined part in the deletion sequence.

This kind of thing seems difficult to achieve. But let's consider it in turn. Consider each point from small to large, and open up the path from it to the largest point (opening up means that only the edges on this path are retained, while the other edges of the points on this path are hidden). Because the path of a larger point will be opened later, the final connected chain with a point as the bottom end is the path from this point to its previously determined part.

The so-called "get through" is the Access operation in LCT when the maximum point is the root.

Therefore, as long as we maintain these connected chains and sort them according to the bottom number, the ranking of a point in the deletion sequence is the sum of the sizes of all connected chains before its chain plus its ranking in the chain.

This can be maintained by a tree array with the bottom number as the subscript.

Processing modification operations

Considering the modification operation, the operated point must become the maximum point.

Find out the path between it and the original maximum point. According to the previous conclusion, they will be deleted at last and should form a new connected chain.

The rest of the connected chain will not change after removing the part between the existing maximum point and the original maximum point.

Therefore, in fact, you only need to change the root to the current maximum point, and then open the path from the original maximum point to the current maximum point.

Code: \ (O(n\log n) \)

#include<bits/stdc++.h>
#define Tp template<typename Ty>
#define Ts template<typename Ty,typename... Ar>
#define Rg register
#define RI Rg int
#define Cn const
#define CI Cn int&
#define I inline
#define W while
#define N 200000
using namespace std;
int n;
namespace FastIO
{
	#define FS 100000
	#define tc() (FA==FB&&(FB=(FA=FI)+fread(FI,1,FS,stdin),FA==FB)?EOF:*FA++)
	#define pc(c) (FC==FE&&(clear(),0),*FC++=c)
	int OT;char oc,FI[FS],FO[FS],OS[FS],*FA=FI,*FB=FI,*FC=FO,*FE=FO+FS;
	I void clear() {fwrite(FO,1,FC-FO,stdout),FC=FO;}
	Tp I void read(Ty& x) {x=0;W(!isdigit(oc=tc()));W(x=(x<<3)+(x<<1)+(oc&15),isdigit(oc=tc()));}
	Ts I void read(Ty& x,Ar&... y) {read(x),read(y...);}
	I void readc(char& x) {W(isspace(x=tc()));}
	Tp I void writeln(Ty x) {W(OS[++OT]=x%10+48,x/=10);W(OT) pc(OS[OT--]);pc('\n');}
}using namespace FastIO;
int Tsz;struct TreeArray//Tree array
{
	int a[2*N+5];I void A(RI x,CI v) {if(!~x) return;W(x<=Tsz) a[x]+=v,x+=x&-x;}
	I int Q(RI x) {RI t=0;W(x) t+=a[x],x-=x&-x;return t;}
}T;
class LinkCutTree
{
	private:
		#define IR(x) (O[O[x].F].S[0]^x&&O[O[x].F].S[1]^x)
		#define Wh(x) (O[O[x].F].S[1]==x)
		#define Co(x,y,d) (O[O[x].F=y].S[d]=x)
		#define PU(x) (O[x].Sz=O[O[x].S[0]].Sz+O[O[x].S[1]].Sz+1)
		#define PD(x) (O[x].P&&(Ts(O[x].S[0],O[x].P),Ts(O[x].S[1],O[x].P),O[x].P=0),O[x].R&&(Re(O[x].S[0]),Re(O[x].S[1]),O[x].R=0))
		#define Ts(x,v) (O[x].G=O[x].P=v)
		#define Re(x) (x)&&(swap(O[x].S[0],O[x].S[1]),O[x].R^=1)
		int St[N+5];struct node {int Sz,G,P,F,R,S[2];}O[N+5];
		I void Ro(RI x) {RI f=O[x].F,p=O[f].F,d=Wh(x);!IR(f)&&(O[p].S[Wh(f)]=x),O[x].F=p,Co(O[x].S[d^1],f,d),Co(f,x,d^1),PU(f);}
		I void S(RI x) {RI f=x,T=0;W(St[++T]=f,!IR(f)) f=O[f].F;W(T) PD(St[T]),--T;W(!IR(x)) f=O[x].F,!IR(f)&&(Ro(Wh(x)^Wh(f)?x:f),0),Ro(x);PU(x);}
		I int FR(RI x) {Ac(x),S(x);W(O[x].S[0]) PD(x),x=O[x].S[0];return S(x),x;}
	public:
		I void Init() {O[0].G=-1;for(RI i=1;i<=n;++i) O[i].G=-1,O[i].Sz=1;}//initialization
		I void Link(CI x,CI y) {MR(x),O[x].F=y;}I void MR(CI x) {Ac(x),S(x),Re(x);}
		I int Q(CI x) {return S(x),T.Q(O[x].G-1)+O[O[x].S[1]].Sz+1;}//Sum of the sizes of all previous connected chains + ranking in the chain
		I void Ac(RI x,CI tg=-1)//Get through and mark it as tg
		{
			RI y;for(y=0;x;x=O[y=x].F) S(x),T.A(O[x].G,-O[x].Sz),T.A(O[O[x].S[1]].G,O[O[x].S[1]].Sz),O[x].S[1]=y,PU(x);//Get through and disconnect from your right son
			Ts(y,tg),T.A(tg,O[y].Sz);//Mark the new connected chain as tg
		}
}LCT;
int main()
{
	RI Qt,i,x,y;for(read(n,Qt),Tsz=n+Qt,LCT.Init(),i=1;i^n;++i) read(x,y),LCT.Link(x,y);
	for(LCT.MR(n),i=1;i^n;++i) LCT.Ac(i,i);//Take the maximum point as the root and connect the path from each point to the maximum point from small to large
	char op;RI rt=n,tt=n;W(Qt--)
	{
		if(readc(op),read(x),op=='u') {rt^x&&(LCT.MR(x),LCT.Ac(rt,tt),rt=x,++tt);continue;}//modify
		op=='w'?writeln(LCT.Q(x)):(read(y),writeln(LCT.Q(x)<LCT.Q(y)?x:y));//Ask and judge the position ratio of direct inquiry
	}return clear(),0;
}