← 返回题目列表

Codeforces · 1146/C

C. 树直径

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

有一个带 $$$n$$$ 节点和 $$$n-1$$$ 边的加权树。节点被方便地标记为从 $$$1$$$ 到 $$$n$$$。权重最多为 $$$100$$$ 正整数。将两个节点之间的距离定义为节点之间唯一路径上的边之和。您想找到树的直径。直径是一对节点之间的最大距离。

不幸的是,这棵树没有给你,但你可以问一些关于它的问题。在一个问题中,您可以指定两个非空不相交的节点集 $$$p$$$ 和 $$$q$$$,判断器将返回 $$$p$$$ 中的节点与 $$$q$$$ 中的节点之间的最大距离。换句话说,$$$x$$$ 和 $$$y$$$ 之间的最大距离,其中 $$$x \in p$$$ 和 $$$y \in q$$$。在询问不超过 $$$9$$$ 问题后,您必须报告任意一对节点之间的最大距离。

互动

每个测试包含多个测试用例。第一行包含测试用例的数量 $$$t$$$ ($$$1 \le t \le 1\,000$$$)。测试用例的描述如下。

每个测试用例的第一行包含一个整数 $$$n$$$ ($$$2 \leq n \leq 100$$$) — 树中的节点数。

要提出问题,请打印 "$$$k_1\ k_2\ a_1\ a_2\ \ldots\ a_{k_1}\ b_1\ b_2\ \ldots\ b_{k_2}$$$" $$$(k_1, k_2 \geq 1$$$ 和 $$$k_1+k_2 \leq n$$$)。这两个集合必须是非空且不相交的。法官将返回一个整数 $$$\max_{p,q} dist(a_p, b_q)$$$。如果您得到 $$$-1$$$ 的结果(因为您打印了无效的查询),请立即退出以避免得到其他结论。

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

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

当您准备好回答时,请打印“$$$-1\ d$$$”,其中 $$$d$$$ 是所有节点对上的最大最短距离。

每个测试用例最多只能提出 $$$9$$$ 问题。

黑客格式

要破解,请使用以下格式。请注意,您只能使用一个测试用例进行破解。

第一行应包含单个整数 $$$t$$$ ($$$t=1$$$)。

第二行应包含单个整数 $$$n$$$ ($$$2 \leq n \leq 100$$$)。

接下来的 $$$n-1$$$ 行应包含三个整数 $$$a_i, b_i, c_i$$$ ($$$1\leq a_i, b_i\leq n$$$, $$$1 \leq c_i \leq 100$$$)。这表示节点 $$$a_i$$$ 和 $$$b_i$$$ 之间的无向边,权重为 $$$c_i$$$。这些边必须形成一棵树。

示例

输入 #1

2
5
9
6
10
9
10
2
99

输出 #1

1 4 1 2 3 4 5
1 4 2 3 4 5 1
1 4 3 4 5 1 2
1 4 4 5 1 2 3
1 4 5 1 2 3 4
-1 10
1 1 1 2
-1 99

注意

在第一个示例中,第一棵树如下所示:

在第一个问题中,我们有 $$$p = {1}$$$,$$$q = {2, 3, 4, 5}$$$。 $$$p$$$ 中的节点与 $$$q$$$ 中的节点之间的最大距离为 $$$9$$$(节点 $$$1$$$ 和 $$$5$$$ 之间的距离)。

第二棵树有两个节点,节点之间有一条边,权重为 $$$99$$$。