交互题
一棵树，一开始只有 1 号点是已知的，其他的都是未知的，你可以调用函数 explore(x,y) ，其中 x 必须是已知的，函数会找到 x 到 y 路径上第二个点，并把它标成已知，求最小步数使整棵树都已知
对于 30% 的数据，是一条链，操作次数 $O(n+logn)$
剩下的数据，操作次数 $O(nlogn)$
$n leq 300000$
sol：
先吐槽 loj 的交互题评测机制
把 ac 时应该输出的东西输出，然后就 a 了
不 shing 话
链的情况想了半天，题解是 xjb 暴力，服
因为这个 explore 的性质，当前已知的一定是一条线段
维护一下当前已知的左端点和右端点，每次随机一个未知的点蹦过去，如果走错方向了就换个方向走
这样出错次数期望 log ？ 不知道
树的情况很好想
首先想到一个很朴素的暴力，对于每个点，从根 explore 下去
然后会发现自己多 explore 了很多已知的点，当需要 explore 一个点的时候你只需要跳到他那个子树上，从那个点开始 explore 就可以了
现在就是要维护一棵树滋磁
1.加入一个点
2.快速跳到一个点
动态点分治/LCT 都可以
但谁都知道 LCT 好写吧...于是果断 LCT
每次操作后 access 保证复杂度即可
至于为什么 access？道理相当于 splay 每次把查询点旋到根保证复杂度？
什么？uoj 有 hack 数据？random_shuffle 一下就可以了
跑到了 rk#3 应该是比较欧的原因
因为之后再也跑不了那么快了
#include <bits/stdc++.h> #include "rts.h" #define LL long long #define rep(i, s, t) for (register int i = (s), i##end = (t); i <= i##end; ++i) #define dwn(i, s, t) for (register int i = (s), i##end = (t); i >= i##end; --i) using namespace std; inline int read() { int x = 0, f = 1; char ch; for (ch = getchar(); !isdigit(ch); ch = getchar()) if (ch == '-') f = -f; for (; isdigit(ch); ch = getchar()) x = 10 * x + ch - '0'; return x * f; } const int maxn = 300010; #define ls ch[x][0] #define rs ch[x][1] int vis[maxn], pid[maxn]; int fa[maxn], ch[maxn][2], mn[maxn], mx[maxn]; inline int isroot(int x) { return ((ch[fa[x]][0] != x) && (ch[fa[x]][1] != x)); } inline void pushup(int x) { mn[x] = mx[x] = x; if (ls) mn[x] = mn[ls]; if (rs) mx[x] = mx[rs]; } inline void rotate(int x) { int y = fa[x], z = fa[y]; int l = (ch[y][1] == x), r = l ^ 1; if (!isroot(y)) ch[z][ch[z][1] == y] = x; fa[x] = z; fa[ch[x][r]] = y; fa[y] = x; ch[y][l] = ch[x][r]; ch[x][r] = y; pushup(y); pushup(x); } inline void splay(int x) { while (!isroot(x)) { int y = fa[x], z = fa[y]; if (!isroot(y)) { if (ch[z][0] == y ^ ch[y][0] == x) rotate(x); else rotate(y); } rotate(x); } pushup(x); } void access(int x) { for (int y = 0; x; y = x, x = fa[x]) { splay(x); rs = y; pushup(x); } } inline int findroot(int x) { while (!isroot(x)) x = fa[x]; return x; } void play(int n, int T, int dataType) { // srand((unsigned long long)new char); for (int i = 2; i <= n; i++) pid[i] = i; random_shuffle(pid + 2, pid + n + 1); if (dataType == 3) // chain { vis[1] = 1; int l = 1, r = 1; for (int i = 2; i <= n; i++) { int x = pid[i], now; if (vis[x]) continue; if (!vis[now = explore(l, x)]) { while (now != x) vis[now] = 1, now = explore(now, x); vis[x] = 1; l = x; } else { now = explore(r, x); while (now != x) vis[now] = 1, now = explore(now, x); vis[x] = 1; r = x; } } } else { vis[1] = 1; mn[1] = mx[1] = 1; for (int i = 2; i <= n; i++) { if (vis[pid[i]]) continue; int now = pid[i], x = findroot(1), ret; while (!vis[now]) { ret = explore(x, now); if (mn[rs] == ret) x = rs; else if (mx[ls] == ret) x = ls; else if (vis[ret]) x = findroot(ret); else vis[ret] = 1, mn[ret] = mx[ret] = ret, fa[ret] = x, x = ret; } access(now); } } }