交互题，给一颗 $N$ 点仙人掌，系统选好一个点 $x$ 后让选手猜这个点，猜中结束，没猜中的话返回选手所猜点 $u$ 的一个邻接点 $w$，保证 $w$ 到 $x$ 的最短路距离 $dist(w, x)$ 严格小于 $dist(u, x)$，每组数据选 $N$ 次点，每次选点最多猜 $10$ 次，$N\le 500$

如果能做到每次猜一个点，不管系统如何回复，都可以淘汰掉至少一半的候选点，那这题就可以做了。

如何满足这样的猜点？

对于每次猜点，选择所有候选点中离其他候选点距离和最小的点，即可。

小证一下

反证法，如果一次猜点后，没能淘汰一半的点，说明一半以上的候选点 $i$ 满足 $dist(i,w)<dist(i,u)$，这说明 $w$ 离其他候选点的距离和更小，$u$ 并不是距离和最小的点。

因此预处理一下两两之间的距离，对于每组询问复杂度是 $N^2+\frac{N^2}{4}+\frac{N^2}{16}+\dots < 2\times N^2$。总共 $N$ 次询问，总复杂度 $O(N^3)$

实际上第一次猜点一定是固定的，不用每次询问重复求，剪掉这个后常数非常小，跑的飞快。