CF2277E Tree Guessing

[Maozon - Stasis](https://www.youtube.com/watch?v=seY45BJkUQE) 这是一个交互题。 交互器有一棵隐藏的 $n$ 个点的树，点编号为 $1$ 到 $n$。你的任务是在不超过 $2n-2$ 次查询内找出这棵树。 每次查询时，你需要选择一个点 $x$，以及 $1$ 到 $n$ 的一个排列 $p_1, p_2, \ldots, p_n$，交互器会返回 $$ \sum_{i = 1}^{n} \max_{j \in \text{path}(i, x)} p_j, $$ 其中 $\text{path}(i, x)$ 表示从 $i$ 到 $x$ 的简单路径上所有的点集合，包括 $i$ 和 $x$（特别地，$\text{path}(x, x) = \{x\}$）。 换句话说，对于每个点 $i$，考虑从 $i$ 到 $x$ 的唯一简单路径上的所有点 $j$，取这些点对应的 $p_j$ 的最大值。对每个 $i$ 求出上述最大值后求和，作为本次的交互器返回值。

每个测试包含多组数据。第一行为测试组数 $t$（$1 \le t \le 250$）。每组数据描述如下。 每组数据的第一行包含一个整数 $n$（$2 \le n \le 500$），表示树的顶点数。 保证所有测试中 $n$ 的总和不超过 $500$。

【交互题，无需填写。】

在第一个测试样例中，唯一可能的两点树只有一条边 $(1, 2)$，因此无需查询即可确定结构。答案为 !，随后输出这条边。 在第二个测试样例中，树有两条边，分别为 $(1, 2)$ 和 $(1, 3)$。 在第一次查询中，$x = 1$，$p = [1, 2, 3]$，交互器返回 $\max\{1\} + \max\{2, 1\} + \max\{3, 1\} = 6$。 在第二次查询中，$x = 2$，$p = [1, 2, 3]$，交互器返回 $\max\{1, 2\} + \max\{2\} + \max\{3, 1, 2\} = 7$。 由 ChatGPT 5 翻译