← 返回题目列表

Codeforces · 1592/D

D. ICPC 中的血红素?

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

这是一个交互问题!

在上届地区比赛 Hemose 中,Carpe Diem 团队成员 ZeyadKhattab 和 YahiaSherif 由于某些未知原因没有获得 ICPC 资格。 Hemose 非常伤心,赛后度过了糟糕的一天,但 ZeyadKhattab 非常明智,非常了解 Hemose,不想看到他伤心。

Zeyad 知道 Hemose 喜欢树问题,所以他用一个非常特殊的设备给了他一个树问题。

Hemose 有一个带 $$$n$$$ 节点和 $$$n-1$$$ 边的加权树。不幸的是,Hemose 不记得边的权重。

让我们将 $$$u\neq v$$$ 的 $$$Dist(u, v)$$$ 定义为从节点 $$$u$$$ 到节点 $$$v$$$ 的路径上所有边的权重的最大公约数。

Hemose 有一个特殊的装置。 Hemose 可以为设备提供一组节点,设备将返回该组中任意两个节点之间最大的 $$$Dist$$$。更正式地说,如果 Hemose 为设备提供一组 $$$S$$$ 节点,则设备将返回所有对 $$$(u, v)$$$ 中 $$$Dist(u, v)$$$ 的最大值,其中 $$$u$$$、$$$v$$$ $$$\in$$$ $$$S$$$ 和 $$$u \neq v$$$。

Hemose 最多可以使用该设备 $$$12$$$ 次,并且想要找到任意两个不同的节点 $$$a$$$, $$$b$$$,使得 $$$Dist(a, b)$$$ 是最大可能的。你能帮助他吗?

互动

从读取单个整数 $$$n$$$ ($$$2 \le n \le 10^3$$$) 开始交互 - 树中的节点数。

接下来,读取 $$$n-1$$$ 行。

接下来的 $$$n-1$$$ 行中的第 $$$i$$$ 包含两个整数 $$$u_i$$$ 和 $$$v_i$$$ ($$$1 \leq u_i, v_i \leq n$$$, $$$u_i\neq v_i$$$),这意味着节点 $$$u_i$$$ 和 $$$u_i$$$ 之间有一条边$$$v_i$$$。

保证边的权重为$$$\leq 10^9$$$。

保证给定的图是一棵树。

现在您可以开始提问。要询问一组 $$$k$$$ 节点 $$$v_1, v_2, \ldots, v_k$$$($$$2 \le k \le n$$$, $$$1 \le v_i \le n$$$,所有 $$$v_i$$$ 都是不同的),输出:

? $$$k$$$ $$$v_1$$$ $$$v_2$$$ $$$\ldots$$$ $$$v_k$$$

然后您将收到一个整数 $$$x$$$,即 $$$1 \le i, j \le k$$$ 和 $$$i \neq j$$$ 上最大的 $$$Dist(v_i, v_j)$$$。

当您找到 $$$a$$$ 和 $$$b$$$ ($$$1 \le a, b \le n)$$$, $$$a\neq b$$$) 使得 $$$Dist(a, b)$$$ 是可能的最大值时,按以下格式打印答案:

! $$$a$$$$$$b$$$

输出答案不计入 $$$12$$$ 查询的限制。

如果有多对 $$$(a, b)$$$ 具有相同的最大 $$$Dist(a, b)$$$,则可以输出任何一个。

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

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

黑客

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

第一行应包含一个整数 $$$n$$$ $$$(2 \leq n \le 10^3)​​$$$ — 节点数。

接下来的 $$$n-1$$$ 行中的第 $$$i$$$ 应包含三个整数 $$$u_i$$$, $$$v_i$$$, $$$w_i$$$ ($$$1 \le u_i, v_i \le n$$$, $$$u_i\ne v_i$$$, $$$1 \le w \le 10^9$$$),这意味着节点 $$$u_i$$$ 和 $$$v_i$$$ 之间有一条边,权重为 $$$w_i$$$。

这些 $$$n-1$$$ 边必须形成一棵树。

示例

输入 #1

6
1 2
2 3
2 4
1 5
5 6

10

2

10

输出 #1

? 6 1 2 3 4 5 6

? 3 3 1 5

? 2 1 2

! 1 2

注意

第一个样本中的树: