题目描述
小M在玩一个即时战略(Real Time Strategy)游戏。不同于大多数同类游戏，这个游戏的地图是树形的。
也就是说，地图可以用一个由 n个结点，n?1条边构成的连通图来表示。这些结点被编号为 1 ~ n。
每个结点有两种可能的状态：“已知的”或“未知的”。游戏开始时，只有 1号结点是已知的。在游戏的过程中，小M可以尝试探索更多的结点。具体来说，小M每次操作时需要选择一个已知的结点 x，和一个不同于 x 的任意结点 y（结点 y 可以是未知的）。
然后游戏的自动寻路系统会给出 x 到 y 的最短路径上的第二个结点 z，也就是从 x 走到 y 的最短路径上与 x 相邻的结点。此时，如果结点 z 是未知的，小M会将它标记为已知的。
这个游戏的目标是：利用至多 T 次探索操作，让所有结点的状态都成为已知的。然而小M还是这个游戏的新手，她希望得到你的帮助。
题解
论手残选手如何写交互写挂到死UOJ上交了两页多。。。
为了骗分不被hack，可以把所有点打乱顺序。
对于地图是一条链的情况，我们可以可以维护当前拓展出的区间，然后每次暴力更新。
然后树的情况，比较好的做法是搞一个动态点分树，可以保证每次拓展的复杂度都是log的。
或者写LCT，它的拓展复杂度是基于splay的，均摊log，会被hack。
为了用LCT过掉这道题，需要把某些函数写的奇怪一点。
inline int findroot(int x){ while(!isroot(x))x=fa[x]; // splay(x); return x; }
代码
#include<iostream> #include "rts.h" #include<cstdio> #include<algorithm> #include<ctime> #define ls ch[x][0] #define rs ch[x][1] #define N 300009 using namespace std; int ch[N][2],lc[N],rc[N],fa[N],id[N]; bool vis[N]; inline bool ge(int x){return ch[fa[x]][1]==x;} inline bool isroot(int x){return ch[fa[x]][0]!=x&&ch[fa[x]][1]!=x;} inline void pushup(int x){ lc[x]=rc[x]=x; if(ls)lc[x]=lc[ls]; if(rs)rc[x]=rc[rs]; } inline void rotate(int x){ int y=fa[x],o=ge(x); ch[y][o]=ch[x][o^1];fa[ch[y][o]]=y; if(!isroot(y))ch[fa[y]][ge(y)]=x;fa[x]=fa[y]; fa[y]=x;ch[x][o^1]=y;pushup(y);pushup(x); } inline void splay(int x){ while(!isroot(x)){ int y=fa[x]; if(isroot(y))rotate(x); else rotate(ge(x)==ge(y)?y:x),rotate(x); } } inline void access(int x){ for(int y=0;x;y=x,x=fa[x]){ splay(x);ch[x][1]=y;pushup(x); } } inline int findroot(int x){ while(!isroot(x))x=fa[x]; // splay(x); return x; } inline void work(int x){ int now=findroot(1); while(!vis[x]){ int y=explore(now,x); if(y==lc[ch[now][1]])now=ch[now][1]; else if(y==rc[ch[now][0]])now=ch[now][0]; else if(vis[y])now=findroot(y); else vis[y]=1,fa[y]=now,now=y; } access(x); } void play(int n, int T, int dataType){ srand(12345678); for(int i=1;i<=n;++i)id[i]=i;vis[1]=1; for(int i=1;i<=n;++i)lc[i]=rc[i]=i; for(int i=1;i<=2;++i)random_shuffle(id+2,id+n+1); if(dataType==3){ int L=1,R=1; for(int i=1;i<=n;++i)if(!vis[id[i]]){ int x=id[i]; int now=explore(L,x); if(vis[now]){ while(!vis[x]){ int y=explore(R,x); vis[y]=1;R=y; } } else{ while(!vis[x]){ int y=explore(L,x); vis[y]=1;L=y; } } } return; } else for(int i=2;i<=n;++i)if(!vis[id[i]])work(id[i]); }