有人能解释一下“修路”这个谜题的测试用例吗？

Question

我正试着解决下面的难题。我被一个测试用例弄糊涂了。

以下是问题所在：

拜特朗国家包括N个城市和N-1之间的双向公路，因此在任何两个城市之间都有一条道路。拜特朗的道路是很久以前建造的，现在需要修缮。你被雇来修理所有的道路。你打算通过在一些道路上派遣机器人来做到这一点。每个机器人都将修复他目前所处的道路，然后移动到相邻的一条未修复的道路上。修完后，他会搬到另一条相邻的未修的道路上，修理那条路等等。

两条道路是相邻的，如果他们有相同的城市在他们的一个端点。为了提高效率，没有任何两个机器人能够修复同一条道路，也没有任何一条路可以被两次访问。完成任务所需的最少机器人数量是多少？

输入:第一行包含测试用例的数量，T.T测试用例如下。每个测试用例的第一行包含N，即Byteland中的城市数。城市编号0.n-1.下面的N1线包含了道路的描述.第一条线包含两个整数ai和bi，这意味着有一条道路连接城市与数字ai和bi。

输出:输出T行，每个测试用例对应一行，包含该测试用例所需的答案。

约束:1 <= T <= 20

1 <= N <= 10000

0 <= ai，bi

现在bolow是我感到困惑的测试用例：

1 15 0 11 1 7 1 11 2 11 2 14 3 4 4 10 4 13 4 8 5 13 6. 10 7 9 8 11 正确答案是2，但为什么？

Answer 1

请注意这里“相邻道路”的定义--您不是在寻找机器人只经过每条路一次的遍历。

使用定义，图中有四条“终端道路”，6，10，5，13，2，14和7 9--它们不能在序列的中间，因为它们只有一条相邻的道路。这是第一个迹象表明，您可以通过两个机器人(从其中的两个开始，在另两个结束)。然后请注意，Byteland几乎被分成两个子国家，48-11是唯一的连接道路，所以不能有两个机器人在半部之间通过，这就很自然了，每个机器人都会修复一半。

从这里开始，构建一个示例遍历(颜色-机器人，数字-sequence)是相当简单的，当然还有很多，因为您可以反转开始/结束，并在中间调整一些顺序。

​

​

这一切都是由于墨维兹和我的视觉皮层，但你并没有要求一般的解决方案。

Answer 2

在这个问题中提到，没有任何两个机器人能够修复同一条道路，也没有任何一条道路可以被两次访问。

如果其中一个分支的端点的距离大于向该方向发送机器人所需的距离，则为1>。

端点与任何顶点的2>距离=1，然后不需要任何额外的机器人

​

https://i.stack.imgur.com/o7zm6.png