题目描述
小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][],lc[N],rc[N],fa[N],id[N];
bool vis[N];
inline bool ge(int x){return ch[fa[x]][]==x;}
inline bool isroot(int x){return ch[fa[x]][]!=x&&ch[fa[x]][]!=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^];fa[ch[y][o]]=y;
if(!isroot(y))ch[fa[y]][ge(y)]=x;fa[x]=fa[y];
fa[y]=x;ch[x][o^]=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=;x;y=x,x=fa[x]){
splay(x);ch[x][]=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();
while(!vis[x]){
int y=explore(now,x);
if(y==lc[ch[now][]])now=ch[now][];
else if(y==rc[ch[now][]])now=ch[now][];
else if(vis[y])now=findroot(y);
else vis[y]=,fa[y]=now,now=y;
}
access(x);
}
void play(int n, int T, int dataType){
srand();
for(int i=;i<=n;++i)id[i]=i;vis[]=;
for(int i=;i<=n;++i)lc[i]=rc[i]=i;
for(int i=;i<=;++i)random_shuffle(id+,id+n+);
if(dataType==){
int L=,R=;
for(int i=;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]=;R=y;
}
}
else{
while(!vis[x]){
int y=explore(L,x);
vis[y]=;L=y;
}
}
}
return;
}
else for(int i=;i<=n;++i)if(!vis[id[i]])work(id[i]);
}