CF1761G Centroid Guess

这是一个交互题。 有一棵未知的树，共有 $n$ 个结点，并且恰好有一个重心。你一开始只知道 $n$，你的任务是找出这棵树的重心。 你最多可以询问 $2\cdot10^5$ 次任意两点之间的距离。 注意，交互器是非自适应的。也就是说，每组测试中的树在测试开始前就已经固定，不会根据你的询问发生变化。 如果删除某个结点后，树被分成的每个连通块的结点数都不超过 $\lfloor\frac{n}{2}\rfloor$，那么这个结点被称为重心。

输入的唯一一行包含一个整数 $n$（$3\le n\le 7.5\cdot10^4$），表示树的结点数。

首先读入 $n$ 开始交互。 每次你想询问结点 $u$ 和结点 $v$（$1 \le u, v \le n$）之间的距离时，输出 "? u v"。 当你确定树的重心为 $x$ 时，输出 "! x" 进行报告。 每次输出后不要忘记换行并刷新输出缓冲区，否则会导致“Idleness limit exceeded”错误。具体操作如下： - C++：fflush(stdout) 或 cout.flush() - Java：System.out.flush() - Pascal：flush(output) - Python：stdout.flush() - 其它语言请查阅相关文档。 本题不支持 Hack。 保证本题最多有 $500$ 组测试数据。

下图是样例中树的结构示意图。  由 ChatGPT 4.1 翻译