← 返回题目列表

Codeforces · 1534/D

D. 丢失的树

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

这是一个交互问题。

小多米在狂欢节上遇到了一个尴尬的问题:他必须猜测 $$$n$$$ 节点的未加权树的边缘!树的节点编号从$$$1$$$ 到$$$n$$$。

游戏大师只允许他问一类问题:

- Little Dormi 选择一个节点 $$$r$$$ ($$$1 \le r \le n$$$),游戏主机将回复一个数组 $$$d_1, d_2, \ldots, d_n$$$,其中 $$$d_i$$$ 是从节点 $$$r$$$ 到 $$$i$$$ 的最短路径的长度,对于所有节点$$$1 \le i \le n$$$。

另外,为了让游戏对小多米发起不公平的挑战,游戏管理员最多允许 $$$\lceil\frac{n}{2}\rceil$$$ 问题,其中 $$$\lceil x \rceil$$$ 表示大于或等于 $$$x$$$ 的最小整数。

面对无法猜出树的令人反胃的可能性,小多米需要你的帮助来制定获胜策略!

请注意,游戏主持人在游戏开始前创建树,并且在游戏过程中不会更改它。

输入

输入的第一行包含整数 $$$n$$$ ($$$2 \le n \le 2\,000$$$),即树中的节点数。

然后您将开始交互。

互动

接受输入后,您最多可以进行 $$$\lceil\frac{n}{2}\rceil$$$ 查询。每个查询均以“? r”格式进行,其中 $$$r$$$ 是整数 $$$1 \le r \le n$$$ 表示您要为该查询选择的节点。

然后,您将收到 $$$n$$$ 空格分隔的整数 $$$d_1, d_2, \ldots, d_n$$$,其中 $$$d_i$$$ 是从节点 $$$r$$$ 到 $$$i$$$ 的最短路径的长度,后跟换行符。

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

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

如果您在任何时候进行无效查询或尝试进行超过 $$$\lceil \frac{n}{2} \rceil$$$ 查询,则交互将立即终止,并且您将收到错误答案判决。

黑客

要破解解决方案,请使用以下格式。

第一行包含整数 $$$n$$$ ($$$2 \le n \le 2\,000$$$)。

接下来的 $$$n−1$$$ 行包含两个整数 $$$u$$$ 和 $$$v$$$ ($$$1 \le u,v \le n$$$) 表示 $$$u$$$ 和 $$$v$$$ ($$$u \neq v$$$) 之间的边。这些 $$$n-1$$$ 边必须形成一棵树。

输出

当你的程序找到树时,首先输出一行由单个“!”组成的行。后面是 $$$n-1$$$ 行,每行都有两个空格分隔的整数 $$$a$$$ 和 $$$b$$$,表示连接节点 $$$a$$$ 和 $$$b$$$ 的边 ($$$1 \le a, b \le n$$$)。完成后,刷新输出流后立即正常终止程序。

您可以按任意顺序输出边,并且边 $$$(a,b)$$$ 被视为与边 $$$(b,a)$$$ 相同。回答不被视为询问。

示例

输入 #1

4

0 1 2 2

1 0 1 1

输出 #1

? 1

? 2

!
4 2
1 2
2 3

输入 #2

5

2 2 1 1 0

输出 #2

? 5

!
4 5
3 5
2 4
1 3

注意

这是第一个示例中的树。

请注意,边缘可以按任何顺序输出。

此外,以下是查询示例 $$$1$$$ 中每个节点的答案:

- $$$1$$$: $$$[0,1,2,2]$$$
- $$$2$$$: $$$[1,0,1,1]$$$
- $$$3$$$: $$$[2,1,0,2]$$$
- $$$4$$$: $$$[2,1,2,0]$$$

下面是第二个交互示例中的树。

最后,以下是查询示例 $$$2$$$ 中每个节点的答案:

- $$$1$$$: $$$[0,4,1,3,2]$$$
- $$$2$$$: $$$[4,0,3,1,2]$$$
- $$$3$$$: $$$[1,3,0,2,1]$$$
- $$$4$$$: $$$[3,1,2,0,1]$$$
- $$$5$$$: $$$[2,2,1,1,0]$$$