题意：

给定一棵树，每个点有一个优先级，最开始为每个点的编号
每次选出最小优先级的叶结点并删除，得到一个删除序列 ( 即 \(prufer\) 序 )
每次操作：

• \(up\) \(x\) 将树上 \(x\) 点的优先级变为全部点优先级的最大值 \(+1\)
• \(when\) \(x\) 查 \(x\) 点在当前删除序列中的位置
• \(compare\) \(x\) \(y\) 比较 \(x,y\) 两个点在删除序中的先后
  \(n,m\leq 2\times 10^5\)

原题链接 : CF1137F

\(Solution\)

首先，能处理 \(when\) 时 \(compare\) 就很显然了
重点看 \(up\) 和 \(when\)
经过一定的手玩，（造一棵节点多一点的树，模拟其 \(prufer\) 序），
不难发现有一些很重要的性质：

• \(1\) 、许多点单次删除，能牵涉到许多相连的点的删除，将这些点看做一条链，
  则每个点到优先级最大的点经过的链的数量近似于 \(O(log(n))\) 条（其实能被卡成 \(O(n)\)）
• \(2\)、优先级最大的点总是最后删
• \(3\)、优先级最大的点与优先级次大的点，总是在如 \(1\) 、中所述的一条链上

至于预处理链，只需用小根堆，拓扑一遍，处理出父节点与 \(prufer\) 序，找出相连的，再用平衡树常规操作二分建树
\(2\)、\(3\)很好证明，\(1\) 中的 \(O(log(n))\) 我们姑且算它是对的
有了这些性质，我们再去模拟 \(1\) 号操作，也不难发现，
它本质上就是将要改动的点到根节点一路上的链断出来（原来的链也保留），形成一条新链，
并且原来各个链的相对顺序不变，新链的顺序需返过来
举个例子（ \(a\) 节点括号内的数，代表 \(a\) 在删除序中的位置，右图为左图 \(up\) \(5\) 得来的）：

边权相同的即代表这条链在 \(prufer\) 序中的删除位置的相连区间

原先 \(prufer\) 序：\((2),(3),(\color{red}{5}),(6),(8,\color{red}{1}),(9,\color{red}{7,4}),(10,\color{red}{11})\)
之后 \(prufer\) 序：\((2),(3),(6),(8),(9),(10),(\color{red}{11,4,7,1,5})\)
可以发现，\(up\) \(5\) 后原先在 \(5-11\) 这条链上遇到的 {\(5\)} , {\(1,8\)} , {\(4,7,9\)} , {\(11,10\)} 这几条链中
在 \(5-11\) 的点拎了出来放在最后，顺序也反了过来，这操作后根也应换为 \(5\)
观察到顺序反过来与\(LCT\)中换根操作相似，\(up\) 操作与 \(access\) 十分相像
于是，对每个点查其在删除序中的位置时，
只要处理出每个点所在链在删除序中的最后的位置，再减去这个点所在链中深度比他大的点的个数即可，用 \(LCT\) 可 \(O(log(n))\) 完成
而链的在删除序最后的位置也等同于在这条链前出现的点的个数和，可理解为链的点数的前缀和，用一个树状数组即可

以这种想法再看 \(up\) 时对之前链的点的个数的影响，其实对每条链，只需减去这条链分离出来的点的个数
而形成的新链大小明显是 \(x\) 到之前根的路径上点的个数，直接在树状数组中加上去
于是链的个数不超过 \(n+m\) ,毫无问题
但是一次 \(up\) 仍与路径上经过链的个数有关，理想时 \(up\) 时间复杂度是 \(O(log(n)^2)\)

蒟蒻并不知如何证明均摊时链的个数为 \(O(log(n))\)，树点涂色那题同样有此疑问
如有想法，欢迎留言，鄙人感激不尽

代码（目前洛谷 \(rk1\)）：

#include<bits/stdc++.h>
using namespace std;
const int N=2e5+10;
int n,m,n_,nn,x,y,xx,yy;
int lowbit(int x){return x&(-x);}
struct bit{
	int t[N<<1];
	void update(int x,int v){for(int i=x;i<=n_;i+=lowbit(i))t[i]+=v;}
	int inquiry(int x){int res=0;for(int i=x;i;i-=lowbit(i))res+=t[i];return res;}
}t;
int anc[N],son[N][2],f[N];
int rev[N],v[N],cov[N],size[N];//cov记录每个点所属链的编号
int to[N<<1],nextn[N<<1],h[N],edg;
bool bb[N];
void add(int x,int y){edg++;to[edg]=y;nextn[edg]=h[x];h[x]=edg;}
bool isroot(int x){return son[anc[x]][0]!=x&&son[anc[x]][1]!=x;}
bool p(int x){return son[anc[x]][1]==x;}
void rev_(int x){son[x][0]^=son[x][1]^=son[x][0]^=son[x][1];rev[x]^=1;}
void cov_(int x,int w){cov[x]=v[x]=w;}
void fix(int x){size[x]=size[son[x][0]]+size[son[x][1]]+1;}
void pushdown(int x){
	if(rev[x]){
		if(son[x][0])rev_(son[x][0]);
		if(son[x][1])rev_(son[x][1]);
		rev[x]=0;
	}
	if(cov[x]){
		if(son[x][0])cov_(son[x][0],cov[x]);
		if(son[x][1])cov_(son[x][1],cov[x]);
		cov[x]=0;
	}
}
void rotate(int x){
	int y=anc[x],xx=anc[y];
	bool b=p(x),bb=p(y);
	anc[x]=xx;
	if(!isroot(y))son[xx][bb]=x;
	son[y][b]=son[x][b^1];
	anc[son[x][b^1]]=y;
	son[x][b^1]=y;
	anc[y]=x;
	fix(y);
	fix(x);
	if(xx)fix(xx);
}
void pushall(int x){
	if(!isroot(x))pushall(anc[x]);
	pushdown(x);
}
void splay(int x){
	pushall(x);
	for(int i=anc[x];i=anc[x],!isroot(x);rotate(x))if(!isroot(i)){
		if(p(i)==p(x))rotate(i);
		else rotate(x);
	}
}
int inquiry(int x){
	splay(x);                              //x的删除位置等于
	return t.inquiry(v[x])-size[son[x][0]];//x所属的链的最大删除位置减去x在链之上的点的个数
}
void access(int x){
	for(int y=0;x;y=x,x=anc[x]){
		splay(x);
		t.update(v[x],-size[son[x][0]]-1);//原先x的链减去x及x在链上方的点的数量
		son[x][1]=y;
		fix(x);
	}
}
void makeroot(int x){
	access(x);
	splay(x);
	nn++;
	t.update(nn,size[x]);
	cov_(x,nn);
	rev_(x);
}
int id[N],rk[N],a[N],b[N],w[N];
priority_queue<int> q;
int deg[N],ord[N];
int build(int anc_,int l,int r,int c){//保证树平衡
	if(l>r)return 0;
	int mid=(l+r)>>1;
	int x=a[mid];
	anc[x]=anc_;
	v[x]=c;
	if(l==r){
		size[x]=1;
		return x;
	}
	son[x][0]=build(x,l,mid-1,c);
	son[x][1]=build(x,mid+1,r,c);
	fix(x);
	return x;
}
void pre(){//预处理
	for(int i=1;i<n;i++)scanf("%d%d",&x,&y),deg[x]++,deg[y]++,add(x,y),add(y,x);
	for(int i=1;i<=n;i++)if(deg[i]==1)q.push(-i);
	int k=0;
	while(!q.empty()){//拓扑排序，每次找出优先级最小值的点
		int x=-q.top();
		q.pop();
		bb[x]=1;
		ord[++k]=x;
		w[x]=k;
		for(int i=h[x];i;i=nextn[i]){
			int y=to[i];
			if(bb[y])continue;
			f[x]=y;
			deg[y]--;
			if(deg[y]==1)q.push(-y);
		}
	}
	k=0;
	for(int i=1;i<=n;i++){
		int x=ord[i],y=ord[i+1];
		b[++k]=x;
		if(f[x]!=y||i==n){
			nn++;
			t.update(nn,k);
			for(int i=1;i<=k;i++)a[i]=b[k-i+1];
			build(f[x],1,k,nn);
			k=0;
		}
	}
}
char opt[10];
main(){
	scanf("%d%d",&n,&m);
        n_=n+m;//n_为最大链数，不这么些时需注意while(m--)时m会变
	pre();
	while(m--){
		scanf("%s",opt);
		scanf("%d",&x);
		if(opt[0]=='u')makeroot(x);
		if(opt[0]=='w')printf("%d\n",inquiry(x));
		if(opt[0]=='c'){
			scanf("%d",&y);
			xx=inquiry(x),yy=inquiry(y);
			printf("%d\n",xx<yy?x:y);
		}
	}
}