题目
交互题；
一开始所有点都是黑的，你需要把所有点变白；
explore(u,v)会将u到v路径上的第二个点变白；
一开始只有1号点是白色的，你需要让所有点变白；
对于一条链次数限制(O(n+log n))，普通的树次数限制(O(n log n)) ;
题解
-
orz yww
-
Part 1
-
白色区间一定是一条链，记录左右端点;
-
先假设新点在左边用左端点扩展，如果explore出重复的点，则说明在右边换右端点；
-
这样一直扩展，最坏(O(2n))，期望(O(n+log n))；
-
浪费次数其实可以看成从头开始的上升子序列的长度，考虑(n)放在哪里：
-
期望$E_n= 1 + sum_{i=0}^{n-1} frac{1}{n} E_{i} -> E_n = E_{n-1}+frac{1}{n} $
-
那么有两边就乘二，再随机一下每次默认的方向就乘二分之一还是log的；
-
Part 2
-
只需要找到已知树上的离新点最近的点；
-
可以用在LCT上跳，均摊(n log n)，也可以在动态点分树上跳，严格(n log n)；
-
我只会写LCT，LCT需要维护链顶和链底标号；
-
(不知道该如何描述．．．．．建议看看rk1的代码)
#include<bits/stdc++.h> #include "rts.h" #define il inline using namespace std; const int N=300010; int vis[N],p[N],fa[N],ch[N][2],rev[N],L[N],R[N]; il bool isrt(int x){return ch[fa[x]][0]!=x&&ch[fa[x]][1]!=x;}// il bool isch(int x,int y){return ch[x][0]==y||ch[x][1]==y;}// il int findrt(int x){while(!isrt(x))x=fa[x];return x;}// il void mfy(int x){ swap(ch[x][0],ch[x][1]); swap(L[x],R[x]); rev[x]^=1; }// il void pushdown(int x){ if(rev[x]){ if(ch[x][0])mfy(ch[x][0]); if(ch[x][1])mfy(ch[x][1]); rev[x]^=1; } } il void pushup(int x){ L[x]=R[x]=x; if(ch[x][0])L[x]=L[ch[x][0]]; if(ch[x][1])R[x]=R[ch[x][1]]; }// il void rotate(int x){ int y=fa[x],z=fa[y]; if(!isrt(y))ch[z][ch[z][1]==y]=x; int l=ch[y][1]==x,r=l^1; fa[x]=z;fa[y]=x;fa[ch[x][r]]=y; ch[y][l]=ch[x][r];ch[x][r]=y; pushup(y);pushup(x); }// void push(int x){ static int sta[N],top; while(!isrt(x))sta[++top]=x,x=fa[x]; sta[++top]=x; while(top)pushdown(sta[top--]); }// il void splay(int x){ push(x); for(int y,z;!isrt(x);rotate(x)){ y=fa[x],z=fa[y]; if(!isrt(y))rotate( (ch[y][0]==x)^(ch[z][0]==y) ? x : y ); } }// il void access(int x){ for(int y=0;x;y=x,x=fa[x]){ splay(x); ch[x][1]=y; pushup(x); } }// il void mkrt(int x){access(x);splay(x);mfy(x);}// il void link(int x,int y){fa[y]=x;}// il void solve(int n){ int a[2]={1,1}; for(int i=2;i<=n;++i){ int u=p[i];if(vis[u])continue; int x=rand()%2,v=explore(a[x],u); if(vis[v])x^=1,v=explore(a[x],u); vis[v]=1;while(v!=u)vis[v=explore(v,u)]=1; a[x]=u; } }// void play(int n,int T,int typ){ srand(23333323); for(int i=1;i<=n;++i)p[i]=i; random_shuffle(p+2,p+n+1); if(typ==3){solve(n);return;} vis[1]=1; for(int i=1;i<=n;++i)L[i]=R[i]=i; for(int i=2,lst=1;i<=n;++i){ int u=p[i],v; lst=findrt(1); if(vis[u])continue; while(lst!=u){ v=explore(lst,u); pushdown(lst); if(!vis[v])vis[v]=1,link(lst,v),lst=v; else if(v==R[ch[lst][0]])lst=ch[lst][0]; else if(v==L[ch[lst][1]])lst=ch[lst][1]; else lst=findrt(v); } //mkrt(lst); mkrt会被卡操作常数 access(lst); } return ; }//