CF1137F Matches Are Not a Child's Play
trick题目
考虑变成有根树，把最后删除的点当做根
就是n了
发现，up操作就是换根！
如果不换根？
直接求出序列查询即可
换根？
那么，新根y是最大值，原根x是次大值，
那么一定是把其他的点都直接删掉，最后剩下(x,y)路径的点，从x一路删到y
发现对于其他点删除的相对顺序不变
我们给(x,y)的路径打一个时间戳mx+1也就是当前最大权值+1
开始i的时间戳就是i的初始排名
那么一个点u的排名一定就是：
时间戳小于u的个数+u子树内时间戳和u一样的数
后者一定是一段连接u的链
并且我们发现，同一个时间戳一定连成的一个链，不会断开
这其实就是access！，再修改颜色
LCT进行换根，树状数组维护时间戳为x的数的个数
access换颜色的时候打标记，并且更新树状数组
#include<bits/stdc++.h>
#define reg register int
#define il inline
#define fi first
#define se second
#define mk(a,b) make_pair(a,b)
#define numb (ch^'0')
#define pb push_back
#define solid const auto &
#define enter cout<<endl
#define pii pair<int,int>
using namespace std;
typedef long long ll;
template<class T>il void rd(T &x){
char ch;x=0;bool fl=false;
while(!isdigit(ch=getchar()))(ch=='-')&&(fl=true);
for(x=numb;isdigit(ch=getchar());x=x*10+numb);
(fl==true)&&(x=-x);
}
template<class T>il void output(T x){if(x/10)output(x/10);putchar(x%10+'0');}
template<class T>il void ot(T x){if(x<0) putchar('-'),x=-x;output(x);putchar(' ');}
template<class T>il void prt(T a[],int st,int nd){for(reg i=st;i<=nd;++i) ot(a[i]);putchar('\n');}
namespace Miracle{
const int N=200000+5;
int n,m;
int lim;
struct edge{
int nxt,to;
}e[2*N];
int hd[N],cnt;
priority_queue<int,vector<int>,greater<int> >q;
void link(int x,int y){
e[++cnt].nxt=hd[x];
e[cnt].to=y;
hd[x]=cnt;
}
int f[2*N];
void add(int x,int c){
for(;x<=lim;x+=x&(-x)) f[x]+=c;
}
int query(int x){
int ret=0;
for(;x;x-=x&(-x)) ret+=f[x];
return ret;
}
struct node{
int ch[2],fa;
int rev,tim;
int tag;
int sz;
}t[N];
int du[N];
void dfs(int x,int fa){
t[x].sz=1;
for(reg i=hd[x];i;i=e[i].nxt){
int y=e[i].to;
if(y==fa) continue;
t[y].fa=x;
dfs(y,x);
}
}
#define ls t[x].ch[0]
#define rs t[x].ch[1]
bool nrt(int x){
return (t[t[x].fa].ch[0]==x||t[t[x].fa].ch[1]==x);
}
void pushup(int x){
if(x) t[x].sz=t[ls].sz+t[rs].sz+1;
}
void tag(int x,int c){
t[x].tag=c;
t[x].tim=c;
}
void rev(int x){
t[x].rev^=1;
swap(ls,rs);
}
void pushdown(int x){
if(t[x].rev){
rev(ls);rev(rs);
t[x].rev=0;
}
if(t[x].tag){
tag(ls,t[x].tag);tag(rs,t[x].tag);
t[x].tag=0;
}
}
void rotate(int x){
int y=t[x].fa,d=t[y].ch[1]==x;
t[t[y].ch[d]=t[x].ch[!d]].fa=y;
if(nrt(x)) t[t[x].fa=t[y].fa].ch[t[t[y].fa].ch[1]==y]=x;
else t[x].fa=t[y].fa;
t[t[x].ch[!d]=y].fa=x;
pushup(y);
}
int sta[N];
void splay(int x){
int y=x,z=0;
sta[++z]=y;
while(nrt(y)) y=t[y].fa,sta[++z]=y;
while(z) pushdown(sta[z--]);
while(nrt(x)){
y=t[x].fa,z=t[y].fa;
if(nrt(y)){
rotate((t[y].ch[0]==x)==(t[z].ch[0]==y)?y:x);
}
rotate(x);
}
pushup(x);
}
void access(int x,int c){
for(reg y=0;x;y=x,x=t[x].fa){
splay(x);
add(t[x].tim,-t[ls].sz-1);
add(c,t[ls].sz+1);
t[x].ch[1]=y;
tag(x,c);
pushup(x);
}
}
void makert(int x,int c){
access(x,c);splay(x);rev(x);
}
int rk(int x){
splay(x);
int ret=t[rs].sz+query(t[x].tim-1)+1;
return ret;
}
int main(){
rd(n);rd(m);
lim=n+m;
int x,y;
int rt=n;
for(reg i=1;i<n;++i){
rd(x);rd(y);
++du[x];++du[y];
link(x,y);link(y,x);
}
for(reg i=1;i<=n;++i) if(du[i]==1) q.push(i);
int df=0;
while(!q.empty()){
int x=q.top();q.pop();
t[x].tim=++df;
add(df,1);
for(reg i=hd[x];i;i=e[i].nxt){
int y=e[i].to;
if(du[y]>1){
--du[y];
if(du[y]==1) q.push(y);
}
}
}
dfs(rt,0);
char s[233];
while(m--){
scanf("%s",s+1);
if(s[1]=='u'){
++df;
rd(x);
makert(x,df);
}else if(s[1]=='w'){
rd(x);printf("%d\n",rk(x));
}else{
rd(x);rd(y);
printf("%d\n",rk(x)<rk(y)?x:y);
}
}
return 0;
}
}
signed main(){
Miracle::main();
return 0;
}
/*
Author: *Miracle*
*/
考虑提出来根，然后就是换根
考虑换根对路径(x,y)的影响，发现时间戳很合适！
然后LCTaccess