题面传送门：CF1061F Lost Root。
首先对于一个路径 \(a,b\)，我们可以 \(n\) 次询问得到长度，我发现对于一个深度为 \(dep\) 的 \(k\) 叉树来说，直径长度为 \(2dep-1\)，因此我们可以随机路径来找到直径。
考虑计算一下概率二叉树 \(\frac{2^{dep-2} \times 2^{dep-2}}{(2^{dep}-1)^2}\approx \frac{1}{16}\)，随机个 \(30\) 次基本上就能找到了，而对于 \(k>2\) 叉树随到直径的概率显然更高。
由于根一定在直径上且直径的长度为 \(\log\) 量级，我们可以暴力枚举直径上的点，然后判断离叶子的距离是否为 \(dep\) 即可。
#include<bits/stdc++.h>
#define int long long
#define double long double
using namespace std;
inline int read(){char c=getchar();int f=1,ans=0;while(c<48||c>57) f=(c==45?f=-1:1),c=getchar();while(c>=48&&c<=57) ans=(ans<<1)+(ans<<3)+(c^48),c=getchar();return ans*f;
}
mt19937_64 randd(time(0));
inline int ask(int a,int b,int c){printf("? %lld %lld %lld\n",a,b,c);fflush(stdout);string s;cin>>s;return s=="Yes"?1:0;}
const int N=2010;
int vis[N];
main(){int n=read(),k=read();int dep=0,tmp=n*(k-1)+1;while(tmp!=1) dep++,tmp/=k;while(1){int a=randd()%n+1,b=randd()%n+1,sum=0;for (int i=1;i<=n;i++) sum+=(vis[i]=ask(a,i,b));if (sum==2*dep-1){for (int i=1;i<=n;i++) if (vis[i]){int cnt=0;for (int j=1;j<=n;j++) cnt+=ask(a,j,i);if (cnt==dep){printf("! %lld\n",i);fflush(stdout);return 0;}}}}return 0;
}