← 返回题目列表

Codeforces · 1370/F1

F1. 隐藏的一对(简单版)

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

请注意,简单版本和困难版本之间的唯一区别是查询数量的限制。只有当问题的所有版本都得到解决后,你才能进行黑客攻击。

这是一个交互问题。

给您一棵由 $$$n$$$ 节点组成的树,节点的编号从 $$$1$$$ 到 $$$n$$$ 之间的整数。 Ayush 和 Ashish 在树中选择了两个不同的秘密节点。您需要找出这两个节点。您可以进行以下查询:

- 提供一个节点列表,您将从该列表中收到一个节点,其到两个隐藏节点的距离之和最小(如果列表中有多个此类节点,您将收到其中任何一个)。您还将获得该节点到隐藏节点的距离总和。

回想一下,树是一个没有循环的连通图。两个节点之间的距离定义为它们之间的简单路径中的边数。

更正式地说,我们将两个隐藏节点定义为 $$$s$$$ 和 $$$f$$$。在一个查询中,您可以提供树的一组节点 $$$\{a_1, a_2, \ldots, a_c\}$$$。结果,您将得到两个数字 $$$a_i$$$ 和 $$$dist(a_i, s) + dist(a_i, f)$$$。节点 $$$a_i$$$ 是所提供集合中的任意节点,其中数量 $$$dist(a_i, s) + dist(a_i, f)$$$ 是最小的。

您最多可以提出 $$$14$$$ 查询。

输入

第一行包含一个整数 $$$t$$$ $$$(1 \leq t \leq 10)$$$ — 测试用例的数量。请注意交互过程是如何组织的。

每个测试用例的第一行由一个整数 $$$n$$$ $$$(2 \le n \le 1000)$$$ — 树中的节点数组成。

接下来的 $$$n - 1$$$ 行由两个整数组成 $$$u$$$, $$$v$$$ $$$(1 \le u, v \le n, u \ne v)$$$ - 树的边缘。

互动

要询问查询,请打印一行:

- 在开头打印“? c”(不带引号),其中 $$$c$$$ $$$(1 \leq c \leq n)$$$ 表示正在查询的节点数,后跟 $$$c$$$ 范围内的不同整数 $$$[1, n]$$$ — 列表中节点的索引。

对于每个查询,您将收到两个整数 $$$x$$$,$$$d$$$ - 到隐藏节点的距离总和以及从该节点到隐藏节点的距离总和最小的节点(在查询的节点中)。如果查询的节点子集无效或者超出查询数量,那么您将得到 $$$x = d = -1$$$。在这种情况下,您应该立即终止该程序。

当您猜出隐藏节点后,打印一行“!”(不带引号),后跟 $$$[1, n]$$$ 范围内的两个整数 - 隐藏节点。您可以按任何顺序输出隐藏节点。

之后,您应该读取一个字符串。如果您猜对了节点,您将收到字符串“正确”。在这种情况下,您应该继续解决剩余的测试用例,或者如果解决了所有测试用例,则终止程序。否则,您将收到字符串“不正确”。在这种情况下,您应该立即终止该程序。

猜测隐藏节点不计入询问的查询数量。

交互器不具有自适应性。隐藏节点不会随查询而改变。

猜测隐藏节点后,不要忘记读取字符串“正确”/“错误”。

您需要先解决每个测试用例,然后才能接收下一个测试用例的输入。

$$$14$$$ 查询的限制适用于每个测试用例,而不是整个输入。

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

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

黑客

要破解该解决方案,请使用以下测试格式:

第一行应包含一个整数 $$$t$$$ $$$(1 \leq t \leq 10)$$$ — 测试用例的数量。测试用例的描述如下。

每个测试用例的第一行应包含一个整数 $$$n$$$ $$$(2 \le n \le 1000)$$$ - 树中的节点数。第二行应包含 $$$[1, n]$$$ 范围内的两个不同整数 - 隐藏节点。接下来的 $$$n - 1$$$ 行应包含两个整数 $$$u$$$、$$$v$$$ $$$(1 \le u, v \le n, u \ne v)$$$ — 树的边缘。

示例

输入 #1

1
3
1 2
1 3

1 1

2 3

3 1

3 1

Correct

输出 #1

? 1 1

? 1 2

? 1 3

? 2 2 3

! 1 3

注意

第一次测试的树如下所示,隐藏节点是 $$$1$$$ 和 $$$3$$$。