给定正整数 (n)，交互库有 (n) 个叶子的"满二叉树"（所有点恰有 (0/2) 个儿子），也即 (2n-1) 个点。
每个叶子有 (1-n) 的编号，每次询问 (a_1,a_2,a_3)，交互器告诉你 ( ext{LCA}(a_1,a_2))，( ext{LCA}(a_2,a_3))，( ext{LCA}(a_3,a_1)) 中哪个最浅。
求这棵树，但不需求出编号（给出的树与答案在有根意义下同构即可）。
(nle 10^3)。
点分治？想不到。。。
按顺序把叶子插入，维护虚树。初始时 (n+1) 连向 (1,2)。
设当前要插叶子 (i)，先将当前得到的树点分，每次找到当前连通块的重心 (c)，若 (c) 是叶子那么建新点连向 (c,i)，若 (c) 不是叶子则在左右子树中分别找叶子 (l,r)，询问 (l,r,i) 就可以知道 (i) 在 (c) 的左/右子树还是 (c) 的子树外。递归到对应位置，如果没地方加了就在当前边上建新点连向 (i)。
时间复杂度 (O(n^2))，操作次数 (nlfloorlog_2n floor)。
#include<bits/stdc++.h>
using namespace std;
const int N = 2003;
template<typename T>
bool chmin(T &a, const T &b){if(a > b) return a = b, 1; return 0;}
int n, S, Mn, rt, ct, cnt, siz[N], ch[N][2], fa[N], lef[N];
bool vis[N];
void link(int f, bool c, int x){ch[fa[x] = f][c] = x;}
void fdrt(int x){
if(vis[x]){siz[x] = 0; return;}
int ws;
if(ch[x][0]){
int a = ch[x][0], b = ch[x][1];
fdrt(a); fdrt(b);
siz[x] = siz[a]+siz[b]+1;
ws = max(max(siz[a], siz[b]), S-siz[x]);
} else {
siz[x] = 1; ws = S-1;
}
if(chmin(Mn, ws)) ct = x;
}
void solve(int x, int f, bool c, int u){
vis[x] = true;
int a = ch[x][0], b = ch[x][1], t;
if(a){
printf("%d %d %d
", lef[a], lef[b], u);
fflush(stdout);
do t = getchar(); while(t < 'X' || t > 'Z');
}
if(!a || t == 'X'){
if(!fa[x] || vis[fa[x]]){
if(fa[x]) link(fa[x], c, ++cnt);
else rt = ++cnt;
link(cnt, 0, x); link(cnt, 1, u);
lef[cnt] = lef[u] = u;
} else {
S -= siz[x]; Mn = N;
fdrt(f ? ch[f][c] : rt);
solve(ct, f, c, u);
}
} else {
a = ch[x][t = t == 'Y'];
if(vis[a]){
link(x, t, ++cnt);
link(cnt, 0, a);
link(cnt, 1, u);
lef[cnt] = lef[u] = u;
} else {
S = siz[a]; Mn = N;
fdrt(a); solve(ct, x, t, u);
}
}
}
int main(){
scanf("%d", &n); cnt = n;
link(rt = ++cnt, 0, 1);
link(rt, 1, 2);
lef[1] = lef[rt] = 1;
lef[2] = 2;
for(int i = 3;i <= n;++ i){
memset(vis, 0, sizeof vis);
S = i-2<<1|1; Mn = N;
fdrt(rt); solve(ct, 0, 0, i);
} puts("-1");
for(int i = 1;i <= cnt;++ i)
printf("%d ", fa[i] ?: -1);
}