← 返回题目列表

Codeforces · 1919/H

H. 树直径

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

有一个隐藏的树,有 $$$n$$$ 个顶点。树的 $$$n-1$$$ 边从 $$$1$$$ 到 $$$n-1$$$ 编号。您可以提出以下两种类型的查询:

1. 为评分者提供一个数组 $$$a$$$,其中包含 $$$n - 1$$$ 正整数。对于从 $$$1$$$ 到 $$$n - 1$$$ 的每条边,边 $$$i$$$ 的权重设置为 $$$a_i$$$。然后,分级机将返回直径$$$^\dagger$$$的长度。
2. 给评分者两个索引 $$$1 \le a, b \le n - 1$$$。分级器将返回边 $$$a$$$ 和 $$$b$$$ 之间的边数。换句话说,如果边 $$$a$$$ 连接 $$$u_a$$$ 和 $$$v_a$$$,而边 $$$b$$$ 连接 $$$u_b$$$ 和 $$$v_b$$$,则评分器将返回 $$$\min(\text{dist}(u_a, u_b), \text{dist}(v_a, u_b), \text{dist}(u_a, v_b), \text{dist}(v_a, v_b))$$$,其中 $$$\text{dist}(u, v)$$$ 表示顶点 $$$u$$$ 和 $$$v$$$ 之间路径上的边数。

在最多 $$$n$$$ 类型 1 查询和 $$$n$$$ 类型 2 查询(以任意顺序)之后,找到与隐藏树同构 $$$^\ddagger$$$ 的任何树。

$$$^\dagger$$$ 两个顶点之间的距离是连接它们的唯一简单路径上的权重之和。直径是所有这些距离中最大的。

$$$^\ddagger$$$ 如果存在包含从 $$$1$$$ 到 $$$n$$$ 的整数的排列 $$$p$$$,使得边 ($$$u$$$, $$$v$$$) 出现在第一棵树中当且仅当边($$$p_u$$$, $$$p_v$$$) 出现在第二棵树中。

输入

输入的第一行也是唯一一行包含一个整数 $$$n$$$ ($$$3 \le n \le 1000$$$) — 树中的顶点数。

互动

通过阅读 $$$n$$$ 开始交互。

您可以通过以下方式进行查询:

1. "$$$\mathtt{?}\,1\,a_1\,a_2 \ldots a_{n-1}$$$" ($$$1 \le a_i \le 10^9$$$)。然后,您应该读取一个整数$$$k$$$,它表示直径的长度。您最多只能询问此查询 $$$n$$$ 次。
2. "$$$\mathtt{?}\,2\,a\,b$$$" ($$$1 \le a, b \le n - 1$$$)。然后,您应该读取一个整数 $$$k$$$,它表示边 $$$a$$$ 和 $$$b$$$ 之间的边数。您最多只能询问此查询 $$$n$$$ 次。

如果您的查询无效。该程序将立即终止,您将收到错误答案判决。

要给出最终答案,请打印“!”在一行上,后跟 $$$n - 1$$$ 行,其中 $$$i$$$ 行包含“$$$u_i\,v_i$$$” ($$$1 \le u_i, v_i \le n$$$),这表示对于从 $$$1$$$ 到 $$$n-1$$$ 的每个 $$$i$$$,$$$u_i$$$ 和 $$$u_i$$$ 之间有一条边$$$v_i$$$。

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

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

黑客

第一行包含一个整数 $$$n$$$ ($$$3 \le n \le 1000$$$) — 树中的顶点数。

接下来的 $$$n - 1$$$ 行包含两个整数,每个 $$$u_i, v_i$$$ ($$$1 \le u_i, v_i \le n$$$) - 树的边缘。

示例

输入 #1

5

3

1

9

0

输出 #1

? 1 1 1 1 1

? 2 1 3

? 1 4 3 2 1

? 2 4 2

!
3 1
4 2
1 2
2 5

注意

示例中的隐藏树如上所示。顶点上的数字表示顶点编号,边上的数字表示边编号。

在第一个查询中,所有边都设置为权重 $$$1$$$,因此直径的长度为 $$$3$$$,如图所示。

在第二个查询中,边 $$$1$$$ 和 $$$3$$$ 之间有 $$$1$$$ 边。

在第三个查询中,通过取边 $$$1$$$、$$$2$$$ 和 $$$3$$$,直径为 $$$9$$$。

在第四个查询中,边 $$$4$$$ 和 $$$2$$$ 之间没有边。

示例中给出的答案如上图所示。由于它与隐藏树同构,因此它被接受为正确答案。请注意,边缘可以按任何顺序打印。