题目
题目链接：https://codeforces.com/problemset/problem/1137/F
我们定义一棵树的删除序列为：每一次将树中编号最小的叶子删掉，将该节点编号加入到当前序列的最末端，最后只剩下一个节点时将该节点的编号加入到结尾。
现在给出一棵(n)个节点的树，有(m)次操作：
up v：将(v)号节点的编号变为当前所有节点编号的(max + 1)
when v：查询(v)在当前树的删除序列中是第几号元素
compare u v：查询(u)和(v)在当前树的删除序列中谁更靠前
(n,mleq 2 imes 10^5)。
思路
compare 操作直接求出两个点的排名然后比较一下就好了。
我们发现这个删除序列有一个性质：把删除序列看作一个栈，我们从大到小枚举点 (x)，每次找到 (x) 祖先中深度最深的已经被加入到序列中的点 (y)，那么从 (y) 的儿子到 (x) 路径上的点会依次扔进栈中，最后栈中从栈顶到栈底就是删除序列。
显然最大值是序列的最后一个元素。我们把最大值看作树根，考虑把 (x) 变为最大值之后的影响：把 (x) 看作根，设 (y) 是上一步骤的最大值，显然 (x) 到 (y) 的节点全部会在最后被扔进栈中，然后其他节点的相对位置不变。
这个很像 LCT makert 的过程。也就是我们每次把 (x) 到 (y) 的路径用一个新的编号最大的颜色覆盖，然后对于一个点 (p) 的答案，就是颜色小于 (col_p) 的节点数量，再加上颜色等于 (col_p)，且深度大于 (p) 的节点数量。
那么直接用 LCT 维护就好了。用一个树状数组维护颜色数量的前缀和，询问的时候答案就在树状数组上求前缀和，再加上 Splay 的右子树节点数量。
修改操作就直接把 (x) makert，注意 access 的过程中要修改树状数组。
时间复杂度 (O(mlog^2 n))。
代码
#include <bits/stdc++.h>
using namespace std;
const int N=200010;
int n,m,t,tot,head[N],deg[N];
char typ[10];
struct edge
{
int next,to;
}e[N*2];
void add(int from,int to)
{
e[++tot]=(edge){head[from],to};
head[from]=tot;
}
struct BIT
{
int c[N*2];
void add(int x,int v)
{
if (!x) return;
for (int i=x;i<N*2;i+=i&-i)
c[i]+=v;
}
int query(int x)
{
int ans=0;
for (int i=x;i;i-=i&-i)
ans+=c[i];
return ans;
}
}bit;
struct LCT
{
int fa[N],ch[N][2],siz[N],col[N];
bool rev[N];
bool pos(int x) { return x==ch[fa[x]][1]; }
bool notrt(int x) { return x==ch[fa[x]][0] || x==ch[fa[x]][1]; }
void pushup(int x)
{
siz[x]=siz[ch[x][0]]+siz[ch[x][1]]+1;
}
void pushdown(int x)
{
if (rev[x])
{
int lc=ch[x][0],rc=ch[x][1];
if (lc) swap(ch[lc][0],ch[lc][1]),rev[lc]^=1;
if (rc) swap(ch[rc][0],ch[rc][1]),rev[rc]^=1;
rev[x]=0;
}
if (ch[x][0]) col[ch[x][0]]=col[x];
if (ch[x][1]) col[ch[x][1]]=col[x];
}
void rotate(int x)
{
int y=fa[x],z=fa[y],k=pos(x),c=ch[x][k^1];
if (notrt(y)) ch[z][pos(y)]=x; ch[x][k^1]=y; ch[y][k]=c;
if (c) fa[c]=y; fa[y]=x; fa[x]=z;
pushup(y); pushup(x);
}
void splay(int x)
{
stack<int> st; st.push(x);
for (int i=x;notrt(i);i=fa[i]) st.push(fa[i]);
for (;st.size();st.pop()) pushdown(st.top());
for (;notrt(x);rotate(x))
if (notrt(fa[x])) rotate(pos(x)==pos(fa[x])?fa[x]:x);
}
void access(int x)
{
int y=0;
for (;x;y=x,x=fa[x])
{
splay(x);
bit.add(col[x],-siz[x]+siz[ch[x][1]]);
if (ch[x][1]) col[ch[x][1]]=col[x];
ch[x][1]=y;
pushup(x);
}
col[y]=t;
bit.add(t,siz[y]);
}
void makert(int x)
{
t++;
access(x); splay(x);
swap(ch[x][0],ch[x][1]); rev[x]^=1;
}
int query(int x)
{
splay(x);
return bit.query(col[x]-1)+siz[ch[x][1]]+1;
}
}lct;
void dfs(int x,int fa)
{
lct.fa[x]=fa; lct.siz[x]=1;
for (int i=head[x];~i;i=e[i].next)
{
int v=e[i].to;
if (v!=fa) dfs(v,x);
}
}
void topsort()
{
priority_queue<int> q;
for (int i=1;i<=n;i++)
if (deg[i]==1) q.push(-i);
while (q.size())
{
int u=-q.top(); q.pop();
lct.makert(u);
for (int i=head[u];~i;i=e[i].next)
{
int v=e[i].to;
if (deg[v]>1)
{
deg[v]--;
if (deg[v]==1) q.push(-v);
}
}
}
}
int main()
{
memset(head,-1,sizeof(head));
scanf("%d%d",&n,&m);
for (int i=1,x,y;i<n;i++)
{
scanf("%d%d",&x,&y);
add(x,y); add(y,x); deg[x]++; deg[y]++;
}
dfs(1,0);
topsort();
while (m--)
{
scanf("%s",typ);
if (typ[0]=='u')
{
int x;
scanf("%d",&x);
lct.makert(x);
}
if (typ[0]=='w')
{
int x;
scanf("%d",&x);
printf("%d
",lct.query(x));
}
if (typ[0]=='c')
{
int x,y;
scanf("%d%d",&x,&y);
printf("%d
",lct.query(x)<lct.query(y)?x:y);
}
}
return 0;
}