← 返回题目列表

Codeforces · 1305/D

D. 库罗尼和庆典

中文机器翻译题面 查看原题

这是一个交互问题。

在一道几何题超过 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

注意

请注意,示例交互包含额外的空行,以便更容易阅读。真正的交互不包含任何空行,您也不应该打印任何额外的空行。

下图演示了示例测试中的树: