这是一个交互问题。
在一道几何题超过 13 次时限后获得 AC 后,Kuroni 前往一家意大利餐厅庆祝这一神圣成就。不幸的是,多余的酱汁让他迷失了方向,他现在迷路了!
美利坚合众国可以建模为一棵具有 $$$n$$$ 个顶点的树(为什么)。该树的根位于顶点$$$r$$$,那里是库罗尼的酒店。
Kuroni 有一款手机应用程序,旨在帮助他应对此类紧急情况。要使用该应用程序,他必须输入两个顶点 $$$u$$$ 和 $$$v$$$,它将返回一个顶点 $$$w$$$,它是这两个顶点的最低公共祖先。
然而,由于Kuroni直播庆祝派对时手机电量几乎耗尽,他最多只能使用该应用程序$$$\lfloor \frac{n}{2} \rfloor$$$次。之后,手机就会死机,我们亲爱的朋友就没有任何帮助了! :(
由于夜晚又冷又黑,库罗尼需要回来,以便他可以与舒适的床和枕头团聚。你能帮他找出酒店的位置吗?
互动
交互从读取单个整数 $$$n$$$ ($$$2 \le n \le 1000$$$) 开始,即树的顶点数。
然后你会读到 $$$n-1$$$ 行,其中第 $$$i$$$ 有两个整数 $$$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$$$ 并完成交互。您将收到错误答案判决。确保立即退出,以避免得到其他判决。
当找到顶点 $$$r$$$ 时,打印“! $$$r$$$”并退出。此查询不计入 $$$\lfloor \frac{n}{2} \rfloor$$$ 限制。
请注意,树是预先固定的,并且在查询期间不会改变,即交互器不具有自适应性。
打印任何查询后,不要忘记打印行尾并刷新输出。否则,您可能会超出空闲限制。为此,请使用:
- C++ 中的 fflush(stdout) 或 cout.flush();
- Java 中的 System.out.flush();
- 帕斯卡刷新(输出);
- Python 中的 stdout.flush() ;
- 请参阅其他语言的文档。
黑客
要破解,请使用以下格式:
第一行应包含两个整数 $$$n$$$ 和 $$$r$$$ ($$$2 \le n \le 1000$$$, $$$1 \le r \le n$$$),分别表示顶点数和包含 Kuroni's hotel 的顶点。
接下来的 $$$n-1$$$ 行中的第 $$$i$$$ 行应包含两个整数 $$$x_i$$$ 和 $$$y_i$$$ ($$$1 \le x_i, y_i \le n$$$) - 表示有一条边连接顶点 $$$x_i$$$ 和 $$$y_i$$$。
呈现的边应形成一棵树。
示例
输入 #1
6 1 4 4 2 5 3 6 3 2 3 3 4 4
输出 #1
? 5 6 ? 3 1 ? 1 2 ! 4
注意
请注意,示例交互包含额外的空行,以便更容易阅读。真正的交互不包含任何空行,您也不应该打印任何额外的空行。
下图演示了示例测试中的树: