CF1370F2 The Hidden Pair (Hard Version)

请注意，简单版与困难版的唯一区别在于查询次数的限制。只有在所有版本都被解决的情况下，你才能进行 Hack。 这是一个交互题。 给定一棵包含 $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$ 是你提供的集合中距离之和最小的节点。 你最多只能进行 $11$ 次查询。

第一行包含一个整数 $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$ 是该节点到两个隐藏节点的距离之和。如果查询的节点集合无效或查询次数超限，你将收到 $x = d = -1$，此时应立即终止程序。 当你猜测出隐藏节点后，输出一行 "! "（不含引号），后接两个 $[1, n]$ 范围内的整数，表示隐藏的两个节点，顺序不限。 此后，你需要读取一个字符串。如果猜测正确，你会收到字符串 "Correct"。此时继续解决剩余测试用例或全部结束。如果猜测错误，你会收到字符串 "Incorrect"，此时应立即终止程序。 猜测隐藏节点不计入查询次数。 交互器是非自适应的。隐藏节点不会随查询改变。 不要忘记在每次输出查询后输出换行并刷新输出缓冲区，否则会因超时被判为 Idleness limit exceeded。具体操作如下： - C++：fflush(stdout) 或 cout.flush() - Java：System.out.flush() - Pascal：flush(output) - Python：stdout.flush() - 其它语言请查阅相关文档 Hack 格式 若要 Hack 其他解法，使用如下输入格式： 第一行包含一个整数 $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$ 和 $3$。  由 ChatGPT 4.1 翻译