P13782 [eJOI 2022] Where Is the Root?

这是一个交互式问题。

给定一棵包含 $n$ 个顶点的树。树是一种图，保证任意两个顶点之间恰好存在一条简单路径。**同时保证至少有一个顶点与不少于 3 个顶点直接相连。** 其中有一个顶点是根节点，你的任务是找出它。为此，你可以进行如下形式的询问： - 给定一个顶点集合 $a_1, a_2, \ldots, a_m$，检查它们的最近公共祖先是否在这个集合中。 对于顶点集合 $S$，若顶点 $v$ 位于从 $S$ 中所有顶点到根的路径上，则称 $v$ 为 $S$ 的公共祖先。集合 $S$ 的最近公共祖先（LCA）是指离根最远的那个公共祖先。 ### 交互说明 交互开始时，首先读入一个整数 $n$（$4 \leq n \leq 500$），表示顶点数量。 接着读入 $n - 1$ 行，每行包含两个整数 $a_i, b_i$（$1 \leq a_i, b_i \leq n$），表示在顶点 $a_i$ 和 $b_i$ 之间有一条边。 保证输入的 $n - 1$ 条边构成一棵树，并且至少有一个顶点的度数不小于 3。 你可以通过如下方式发起询问：先输出 `"?"`，再输出一个整数 $m$，然后输出 $m$ 个互不相同的整数 $a_1, a_2, \ldots, a_m$（$1 \leq m \leq n,\ 1 \leq a_i \leq n$），表示你想要检查的顶点集合。 交互器会返回 `"YES"`，如果它们的 LCA 属于集合 $\{a_1, a_2, \ldots, a_m\}$；否则返回 `"NO"`。 你最多可以询问 1000 次，但分数将取决于你的询问次数。输出最终答案不计入询问次数。请参考评分部分获取详细说明。 当你确认根节点后，输出符号 `"!"`，然后输出一个整数 $v$（$1 \leq v \leq n$），表示根节点。然后终止程序。 在输出每次询问后，不要忘记输出换行并刷新缓冲区。可以使用： - 在 C++ 中使用 `fflush(stdout)` 或 `cout.flush()`； - 在 Python 中使用 `stdout.flush()`。 保证对于每个测试用例，树和其根节点在交互开始前已经固定，交互器不会自适应改变。

无

无

### 样例说明  第一次询问：顶点 $5$ 和 $6$ 的 LCA 是顶点 $3$，不在集合 $\{5, 6\}$ 中，因此返回 `"NO"`。 第二次询问：顶点 $3, 5, 6$ 的 LCA 是顶点 $3$，在集合中，因此返回 `"YES"`。 第三次询问：顶点 $1$ 和 $7$ 的 LCA 是顶点 $4$，不在集合中，因此返回 `"NO"`。 第四次询问：顶点 $4$ 和 $6$ 的 LCA 是顶点 $4$，在集合中，因此返回 `"YES"`。 由此可以推测根节点是顶点 $4$，这就是正确答案。 ### 评分规则 1. （7 分）：$n \leq 9$ 2. （10 分）：$n \leq 30$ 3. （最高 83 分）：$n \leq 500$ 在前两个子任务中，你最多可以询问 1000 次。 在第三个子任务中，设 $k$ 为你在某个测试用例中使用的最大询问次数： - 如果 $k \leq 9$，你将得到 83 分。 - 否则，你将得到： $$ \left\lfloor \max \left(10,\ 83 \cdot \left(1 - \frac{\ln(k - 6)}{7}\right)\right) \right\rfloor $$ 以下是 C++ 代码实现的计分函数： ```cpp ((k