CF1534D Lost Tree

这是一个交互题。 Little Dormi 在嘉年华上遇到了一个尴尬的问题：他必须猜出一个 $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$ 的最小整数。 面对无法猜出树结构的窘境，Little Dormi 需要你的帮助，制定一个必赢的策略！ 注意，主持人在游戏开始前就已经确定了树的结构，并且在游戏过程中不会更改。

输入的第一行包含一个整数 $n$（$2 \le n \le 2000$），表示树的节点数。 接下来你将进入交互环节。

当你的程序确定了树的结构后，首先输出一行仅包含一个感叹号 "!"，随后输出 $n-1$ 行，每行包含两个用空格分隔的整数 $a$ 和 $b$，表示一条连接节点 $a$ 和 $b$ 的边（$1 \le a, b \le n$）。输出完毕后，立即刷新输出流并正常结束程序。 你可以以任意顺序输出这些边，边 $(a,b)$ 和 $(b,a)$ 视为相同。输出答案不计入查询次数。 交互说明 读入输入后，你最多可以进行 $ \lceil\frac{n}{2}\rceil $ 次查询。每次查询格式为 "? r"，其中 $r$ 是你选择的节点编号（$1 \le r \le n$）。 随后你会收到 $n$ 个用空格分隔的整数 $d_1, d_2, \ldots, d_n$，其中 $d_i$ 表示节点 $r$ 到节点 $i$ 的最短路径长度，后跟一个换行。 每次输出查询后不要忘记输出换行并刷新输出流，否则会因超时被判定为 Idleness limit exceeded。可使用如下方法刷新输出： - C++：fflush(stdout) 或 cout.flush() - Java：System.out.flush() - Pascal：flush(output) - Python：stdout.flush() - 其它语言请查阅相关文档。 如果你进行了无效的查询或查询次数超过 $ \lceil \frac{n}{2} \rceil $，交互会立即终止，你会收到 Wrong Answer 判定。 Hack 格式 要 hack 某个解法，请使用如下格式： 第一行包含整数 $n$（$2 \le n \le 2000$）。 接下来 $n-1$ 行，每行包含两个整数 $u$ 和 $v$（$1 \le u,v \le n$），表示一条连接 $u$ 和 $v$ 的边（$u \ne v$）。这 $n-1$ 条边必须构成一棵树。

下面是第一个示例中的树结构。  注意，边的输出顺序可以任意。 此外，以下是对示例 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]$ 由 ChatGPT 4.1 翻译