Description

有一棵n个点的结构未知的树，初始时只有1号点是已被访问的。

你可以调用交互库的询问函数explore(x,y)，其中x是已访问的点，y是任意点。

它会返回x向y方向走第一步的点，如果该点未被访问，则将其标记为已访问。

你需要实现一个函数，它通过接口得到n和T，需要在T次explore操作内将所有的点标记（也就是说走完这棵树）。

要求最严格的两档数据：

n<=300000,T<=300020，且原树为一条链（1号点不一定是端点）。

n<=300000,T<=5000000

Solution

显然我们要将链的情况分开讨论

考虑这样一个做法，我们将编号随机排列，每次找到排列中第一个尚未被访问的点，从当前所在的链端开始explore，若走到的点是未访问的说明这个点就在这一侧，直接一直扩展到目标点。否则说明这个点在链的另一侧，跳到链的另一端一直扩展到目标点。

这样的出错（即链两边跳）的期望次数是\(\log n\)的

大概是因为每次期望都会消掉某一条链的一半这样。

考虑一棵树怎么做。

我们用一个LCT来维护已经扩展出来的树，将1作为根，每一次访问从1开始，在当前所在的prefer链上二分然后explore，若扩展出的点是未访问点则一直怼下去，否则就修改二分区间（实际上在splay上走），如果不在同一条prefer链上就跳到那一条去。

每次找到目标点就access

注意这里需要尽量保持splay的平衡，每次搞出新点都access一下。

具体可以看代码（有些地方可能比较谜，改一点就差很远）

均摊次数就是\(O(n\log n)\)的

Code

#include 
    
     #include "rts.h"#define fo(i,a,b) for(int i=a;i<=b;++i)#define fod(i,a,b) for(int i=a;i>=b;--i)#define N 300005using namespace std;int cnt;bool bz[N];namespace LCT{    int sz[N],r[N],f[N],fn[N],dep[N],t[N][2],li[N],ri[N];    void up(int k)     {        sz[k]=sz[t[k][0]]+sz[t[k][1]]+1;        li[k]=(t[k][0])?li[t[k][0]]:k;        ri[k]=(t[k][1])?ri[t[k][1]]:k;    }    void hb(int p,int x,int y)    {        if(x&&p>=0) t[x][p]=y;        if(y) fn[y]=p,f[y]=x;    }    void rot(int k)    {        int fa=f[k],p=fn[k];        hb(p,fa,t[k][1-p]);        hb(fn[fa],f[fa],k);        hb(1-p,k,fa);        up(fa),up(k);    }    int d[N];    void splay(int k,int x)    {        while(f[k]!=x&&fn[k]!=-1&&f[k]!=0)         {               if(f[f[k]]==x||fn[f[k]]==-1||f[f[k]]==0) rot(k);            else if(fn[k]==fn[f[k]]) rot(f[k]),rot(k);            else rot(k),rot(k);        }        up(k);    }    void access(int k)    {        int r=k;        splay(k,0);        fn[t[k][1]]=-1,t[k][1]=0;        up(k);        while(f[k]!=0)        {            int fa=f[k];            splay(fa,0);            fn[t[fa][1]]=-1,hb(1,fa,k);            up(fa),k=fa;        }        splay(r,0);    }    void link(int x,int y)    {        access(x);f[y]=x,fn[y]=-1,up(y);    }    void fd(int x,int y)    {        splay(x,0);        while(x!=y)        {            cnt++;            int p=explore(x,y);            if(p==ri[t[x][0]]) x=t[x][0];            else if(p==li[t[x][1]]) x=t[x][1];            else            {                if(bz[p]) splay(p,0);                else up(p),link(x,p),bz[p]=1;                x=p;            }        }        access(y);    }}using namespace LCT;int de[N];void solve3(int n,int T){    int x=1,y=1;    int i=1;    while(i<=n-1)    {        int w=explore(x,de[i]);        if(bz[w]) swap(x,y),w=explore(x,de[i]),cnt++;        bz[w]=1;        while(w!=de[i]) w=explore(w,de[i]),bz[w]=1,cnt++;         x=w;        while(i<=n-1&&bz[de[i]]) i++;    }}void play(int n, int T, int dataType) {    memset(bz,0,sizeof(bz));    bz[1]=sz[1]=dep[1]=1;    up(1);    fo(i,2,n) de[i-1]=i,sz[i]=1;    random_shuffle(de+1,de+n);    if(dataType==3) {solve3(n,T);return;}    int i=1,w=1;    while(i<=n-1)    {        fd(1,de[i]);        while(i<=n-1&&bz[de[i]]) i++;    }    n++,n--;}