谁能解释难题“修复道路”的测试用例吗？

Question

我正在尝试解决以下难题。我对其中一个测试用例感到困惑。

这里是问题：

Byteland国家包含N个城市，并且它们之间有N-1条双向道路，因此任何两个城市之间都有一条道路。 Byteland的道路是很久以前修建的，现在需要维修。您已被雇用修理所有道路。您打算通过在某些道路上调度机器人来做到这一点。每个机器人都会修复他当前所在的道路，然后移动到相邻的未修复道路之一。维修完后，他将移至另一条未经维修的道路，对其进行维修，依此类推。

如果两条道路的端点之一处在同一城市，则它们是相邻的。为了使过程高效，没有两个机器人可以维修同一条道路，也不能两次访问道路。完成任务所需的最少机器人数量是多少？

输入：第一行包含测试用例的数量T。每个测试用例的第一行包含N，即Byteland中的城市数。城市编号为0..N-1。以下N-1行包含道路描述。第i行包含两个整数ai和bi，这意味着有一条道路将数字ai和bi连接到城市。

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

约束：1 <= T <= 201 <= N <= 100000 <= ai，bi

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

1150 111 71 112 112 143 44 104 134 85 136 107 98 1111 12

正确答案是2，但是为什么呢？

Answer 1

请注意这里的“相邻道路”的定义-您并不是要在遍历中机器人仅通过每条道路一次。

使用该定义，您在此图中有4条“终端道路”，分别为6 10、5、13、2 14和7 9-它们不能位于序列的中间，因为它们只有一条相邻的道路。这是您可以使用两个机器人的第一个迹象（从其中两个机器人开始，到另外两个机器人结束）。请注意，然后Byteland几乎被划分为两个子国家，唯一的连接道路为4 8 11，因此您不能在两半之间通过两个机器人，这自然会使一个机器人修理一半。

[从那里开始，构造示例遍历是相当琐碎的（颜色-机械手，数字-序列），当然，因为您可以颠倒开始/结束并在两者之间进行某种顺序的排列，所以当然有很多]

全部归因于Graphviz和我的视觉皮层，但无论如何您都没有要求一般的解决方案。

Answer 2

在此问题中提到，没有两个机器人将修过同一条道路，并且没有道路可以被两次访问。1>如果距离分支之一的端点大于在该方向上发送机器人所需的端点。2>端点到任何顶点的距离= 1 =则不需要任何额外的机器人