交互题。
一棵高度为\(h\)的满二叉树（\(n=2^h-1\)），编号顺序打乱。你需要通过至多\(n+420\)次询问操作找出这棵树的根。
询问为\((u,v,w)\)表示以\(w\)为根的\(LCA(u,v)\)。
\(3\le h\le 18\)
显然询问\((u,v,w)\)相当于找到一个点，使得\(u,v,w\)在这个点的不同子树内。因此询问顺序和返回值无关。
自己的辣鸡想法：维护一棵树，增量构造，假设加入点\(x\)，对这棵树重链剖分，每次询问\((S,T,x)\)，\(S,T\)表示重链的两段。如果询问结果\(y\)是出现过的点，则可以确定\(x\)在\(y\)的轻儿子中，继续下去找，这部分总共最劣是\(O(h)\)；如果\(y\)没有出现，就二分出它在哪两个点之间，插进去，并且把\(x\)连向它，这部分最劣是\(O(\lg h)\)。总共的次数\(O(n(h+\lg h))\)，显然过不去，但是可以构出整棵树。
正解：搞一个桶。随机\(420\)个三元组\((u,v,w)\)（三者不相同），设返回值为\(t\)。如果\(t\notin \{u,v,w\}\)，把它加入桶中。然后把桶中出现次数最多的两个点取出来，它们大概率都是根的儿子；然后用\(O(n)\)次询问就可以问出根是什么。
对于某个点\(t\)，记它的三个子树大小为\(s_1,s_2,s_3\)，可以贡献到的三元组个数\(count(t)=s_1s_2s_3\)。
显然叶子和根的\(count\)为\(0\)。剩下的，对于深度为\(i\)的子树，贡献为\((2^{h-i}-1)^2(2^h-2^{h-i+1})\)，由于三个东西和一样，所以和尽量一样时取到最大值，这时候\(i=2\)，也就是根的两个儿子。
using namespace std;
#include <bits/stdc++.h>
#define N (1<<18)+5
mt19937 ran(time(0)^*new(int));
#define random(l,r) (ran()%((r)-(l)+1)+(l))
int h,n;
int c[N];
int query(int u,int v,int w){
int t;
printf("? %d %d %d\n",u,v,w);
fflush(stdout);
scanf("%d",&t);
return t;
}
void answer(int x){
printf("! %d\n",x);
}
int main(){
scanf("%d",&h);
n=(1<<h)-1;
for (int i=1;i<=420;++i){
int u,v,w,t;
do
u=random(1,n),v=random(1,n),w=random(1,n);
while (u==v || v==w || u==w);
fflush(stdout);
t=query(u,v,w);
if (t!=u && t!=v && t!=w)
c[t]++;
}
int fir=1,sec=2;
if (c[fir]<c[sec])
swap(fir,sec);
for (int i=3;i<=n;++i)
if (c[i]>c[fir])
sec=fir,fir=i;
else if (c[i]>c[sec])
sec=i;
for (int i=1;i<=n;++i)
if (i!=fir && i!=sec){
int t=query(fir,sec,i);
if (t==i){
answer(i);
return 0;
}
}
return 0;
}