CF2245G NPC Challenge

这是一个交互题。 现在有一棵隐藏的无向树，共有 $n$ 个顶点。为了找出这棵树，你可以进行如下形式的若干次询问： - 选择一个由不同顶点组成的序列 $a_1, a_2, \ldots, a_k$，其中 $k \ge 1$。 交互器会根据你的序列处理并返回这些顶点的一个子集，记为 $S$。集合 $S$ 的生成过程如下： - 一开始，$S$ 是一个空集。 - 交互器按照你给出的顺序（从 $a_1$ 到 $a_k$）依次处理这些顶点。 - 对于每一个 $a_i$，如果 $a_i$ 与当前 $S$ 中的任意一个顶点之间都没有边，那么就把 $a_i$ 加入 $S$。否则，$a_i$ 会被忽略。 - 最后处理完所有 $k$ 个顶点后，交互器会把集合 $S$ 返回给你。$S$ 以长度为 $k$ 的二进制字符串 $s$ 的形式表示，其中 $s_i = \texttt{1}$ 当且仅当 $a_i \in S$。 你的任务是找出隐藏树的所有 $n-1$ 条边。为增加难度，所有询问中 $k$ 的总和不得超过 $30 \cdot n$。

每个测试点包含多组测试用例。第一行为测试用例数 $t$（$1 \le t \le 100$）。每个测试用例由如下内容组成。 每个测试用例的第一行为一个整数 $n$（$2 \le n \le 10^3$），表示隐藏树的顶点数。 保证所有测试用例中 $n$ 的总和不超过 $10^3$。

无

在第一个测试用例中，隐藏树有 $n=2$ 个顶点，唯一直是 $(1,2)$。 - 首次询问 $a=[1,2]$： - 顶点 $1$ 被处理，$S$ 为空，$1$ 没有邻居在 $S$ 中，所以将 $1$ 加入 $S$，$S=\{1\}$。 - 顶点 $2$ 被处理，其邻居 $1$ 已在 $S$ 中，因此 $2$ 被忽略。 在第二个测试用例中，隐藏树有 $n=5$ 个顶点，树的边为 $(1,2)$，$(2,3)$，$(2,4)$ 和 $(3,5)$。 - 第一次询问 $a=[1,2,5]$： - 顶点 $1$ 被处理，$S$ 为空，将 $1$ 加入 $S$，$S=\{1\}$。 - 顶点 $2$ 被处理，与 $S$ 中顶点 $1$ 有边，因此被忽略。 - 顶点 $5$ 被处理，其唯一邻居为 $3$，不属于 $S$，因此加入 $S$，$S=\{1,5\}$。 - 第二次询问 $a=[5,3,4,2,1]$： - 顶点 $5$ 被处理，$S$ 为空，将 $5$ 加入 $S$，$S=\{5\}$。 - 顶点 $3$ 被处理，与 $5$ 有边，因此被忽略。 - 顶点 $4$ 被处理，唯一邻居为 $2$，不在 $S$ 内，所以 $4$ 加入 $S$，$S=\{4,5\}$。 - 顶点 $2$ 被处理，与 $4$ 有边，因此被忽略。 - 顶点 $1$ 被处理，唯一邻居为 $2$，不在 $S$ 内，所以 $1$ 加入 $S$。 由 ChatGPT 5 翻译