CF1305D Kuroni and the Celebration

这是一个交互题。 在经历了 13 次超时后终于通过了一道几何题，Kuroni 决定去一家意大利餐厅庆祝这一神圣的成就。不幸的是，过多的酱汁让他晕头转向，现在他迷路了！ 美国可以被建模为一棵有 $n$ 个结点的树（为什么呢），树的根结点为 $r$，Kuroni 的酒店就在这里。 Kuroni 有一个手机应用，专为这种紧急情况设计。使用该应用时，他需要输入两个结点 $u$ 和 $v$，应用会返回一个结点 $w$，即这两个结点的最近公共祖先（LCA）。 然而，由于手机电量几乎耗尽（因为直播了 Kuroni 的庆祝派对），他最多只能使用该应用 $ \lfloor \frac{n}{2} \rfloor $ 次。超过这个次数，手机就会关机，再也无法帮助我们的朋友了。 夜晚又冷又黑，Kuroni 需要尽快回到酒店，才能和他舒适的床和枕头团聚。你能帮他找出酒店的位置吗？

首先输入一个整数 $n$（$2 \le n \le 1000$），表示树的结点数。 接下来输入 $n-1$ 行，每行两个整数 $x_i$ 和 $y_i$（$1 \le x_i, y_i \le n$，$x_i \ne y_i$），表示存在一条连接结点 $x_i$ 和 $y_i$ 的边。保证这些边构成一棵树。 然后你可以进行如下格式的查询： `? u v`（$1 \le u, v \le n$），用于查询结点 $u$ 和 $v$ 的最近公共祖先。 每次查询后，读入一个整数 $w$，表示查询结果。 如果你的查询无效，或者查询次数超过 $ \lfloor \frac{n}{2} \rfloor $，程序会输出 $-1$ 并终止交互。你将收到 Wrong answer 判定。此时请立即退出，避免收到其他判定。 当你确定酒店所在结点 $r$ 后，输出 `! r` 并退出。该操作不计入 $ \lfloor \frac{n}{2} \rfloor $ 次查询限制。 注意，树的结构在查询过程中不会改变，即交互器是非自适应的。 每次输出查询后不要忘记输出换行并刷新输出缓冲区，否则可能会收到 Idleness limit exceeded 判定。具体操作如下： - C++：fflush(stdout) 或 cout.flush() - Java：System.out.flush() - Pascal：flush(output) - Python：stdout.flush() - 其它语言请参考相关文档。 Hack 格式： 第一行输入两个整数 $n$ 和 $r$（$2 \le n \le 1000$，$1 \le r \le n$），表示结点数和酒店所在的结点编号。 接下来 $n-1$ 行，每行两个整数 $x_i$ 和 $y_i$（$1 \le x_i, y_i \le n$），表示一条树边。 输入的边应保证构成一棵树。

见输入格式说明。

请注意，示例交互中包含了额外的空行以便阅读。实际交互中不会有任何空行，你也不应输出任何额外的空行。 下图展示了样例测试中的树结构：  由 ChatGPT 4.1 翻译