codeforces1137F Matches Are Not a Child's Play

題面

題意

給出一棵樹，每個點有一個優先級，初始為自己的标号，如果每次删去樹上優先級最低的葉子，将得到一個序列，要求維護有三種操作：

1.将一個點的優先級修改為此時所有點的優先級的最大值+1

2.詢問某個點在序列中的位置

3.詢問兩個點中哪一個點先被删去

做法

首先第三種操作隻要經過兩次二操作即可得到，是以不用管它。

觀察一下第一種操作之後對序列的影響，發現第一次操作就相當于把原來最大節點到修改節點的路徑上的所有點放到最後，其餘不變。

可以考慮用LCT來維護，如果一個splay中所有點的中序周遊為a,b,c,d,e，就表示當點e被删去之後，點d,c,b,a将被依次連續被删去，這樣就可以通過計算左子樹的大小（在計算點被splay到目前根節點後）來計算在同一個splay中在它之後被删的點，對于不同splay的點，肯定是全部在它之前被删或全部在它之後被删，這樣隻要給每一個splay一個标号（初始為該splay中的标号最大值），用權值樹狀數組維護有幾個點的标号比它小即可，每次access順便在樹狀數組上修改一下各個權值的數量

代碼

#include<bits/stdc++.h>
#define N 200100
using namespace std;

int n,m,tt,bj[N],son[N][2],size[N],fa[N];
char str[10];
bool fz[N],dwn[N];
struct Sz
{
    int num[N<<1];
    inline int lb(int u){return u&(-u);}
    inline int add(int u,int v){for(;u<=(n+m);u+=lb(u)) num[u]+=v;}
    inline int ask(int u){int res=0;for(;u;u-=lb(u)) res+=num[u];return res;}
}sz;
vector<int>to[N];

inline bool ar(int u){return u!=son[fa[u]][0]&&u!=son[fa[u]][1];}
inline bool as(int u){return u==son[fa[u]][1];}
inline void up(int now)
{
    int L=son[now][0],R=son[now][1];
    size[now]=size[L]+size[R]+1;
}
inline void down(int now)
{
    int L=son[now][0],R=son[now][1];
    if(fz[now])
    {
	swap(son[now][0],son[now][1]);
	fz[L]^=1,fz[R]^=1;
	fz[now]=0;
    }
    if(dwn[now])
    {
	bj[L]=bj[R]=bj[now];
	dwn[L]=dwn[R]=1;
	dwn[now]=0;
    }
}

inline void rot(int u)
{
    int p=fa[u],d=as(u);
    if(!ar(p)) son[fa[p]][as(p)]=u;
    fa[u]=fa[p];
    fa[p]=u;
    fa[son[u][!d]]=p;
    son[p][d]=son[u][!d];
    son[u][!d]=p;
    up(p),up(u);
}

void Down(int now)
{
    if(!ar(now)) Down(fa[now]);
    down(now);
}

inline void splay(int u)
{
    Down(u);
    for(;!ar(u);)
    {
	int p=fa[u];
	if(!ar(p))
	    as(u)==as(p)?rot(p):rot(u);
	rot(u);
    }
}

inline void acc(int u,int v)
{
    int p,q;
    for(p=u,q=0;p;q=p,p=fa[p])
    {
	splay(p);
	son[p][1]=0,up(p);
	sz.add(bj[p],-size[p]),sz.add(v,size[p]);
	son[p][1]=q,up(p);
	bj[p]=v,dwn[p]=1;
    }
}

void dfs(int now,int last)
{
    int i,t;
    bj[now]=now;
    for(i=0;i<to[now].size();i++)
    {
	t=to[now][i];
	if(t==last) continue;
	fa[t]=now;
	dfs(t,now);
	if(bj[t]>bj[now])
	{
	    bj[now]=bj[t];
	    son[now][1]=t;
	}
    }
    up(now);
    sz.add(bj[now],1);
}

inline int calc(int u)
{
    splay(u);
    int res=sz.ask(bj[u]);
    return res-size[son[u][0]];
}

int main()
{
    int i,j,p,q;
    cin>>n>>m;
    for(i=1;i<n;i++)
    {
	scanf("%d%d",&p,&q);
	to[p].push_back(q);
	to[q].push_back(p);
    }
    dfs(n,-1);
    tt=n;
    for(i=1;i<=m;i++)
    {
	scanf("%s",str);
	if(str[0]=='u')
	{
	    scanf("%d",&p);
	    acc(p,++tt),splay(p),fz[p]^=1;
	}
	else if(str[0]=='c')
	{
	    scanf("%d%d",&p,&q);
	    printf("%d\n",calc(p)<calc(q)?p:q);
	}
	else
	{
	    scanf("%d",&p);
	    printf("%d\n",calc(p));
	}
    }
}