← 返回题目列表

Codeforces · 1761/G

G. 质心猜测

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

这是一个交互问题。

存在一棵由 $$$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”报告。

打印查询后,不要忘记输出行尾并刷新输出。否则,您将超出空闲限制。为此,请使用:

- C++ 中的 fflush(stdout) 或 cout.flush();
- Java 中的 System.out.flush();
- 帕斯卡刷新(输出);
- Python 中的 stdout.flush() ;
- 请参阅其他语言的文档。

在此问题中,黑客被禁用。

保证此问题最多有 $$$500$$$ 测试。

示例

输入 #1

5

2

1

2

3

1

1

1

输出 #1

? 1 2

? 1 3

? 1 4

? 1 5

? 2 3

? 3 4

? 4 5

! 3

注意

这是示例中的树图像。