algorithm - 谁能解释谜题 "Repairing Roads"的测试用例？

Question

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

问题是:

Byteland 的国家包含 N 个城市和它们之间的 N - 1 条双向道路，使得任意两个城市之间都有一条路径。 Byteland 的道路是很久以前修建的，现在需要维修。你被雇来修理所有的道路。您打算通过在某些道路上 dispatch 机器人来做到这一点。每个机器人将修复他当前所在的道路，然后移动到相邻的未修复道路之一。修好那条路后，他会移动到另一条相邻的未修路，修那条路，依此类推。

如果两条道路的其中一个端点位于同一城市，则两条道路相邻。为了使过程高效，没有两个机器人可以修同一条路，也没有路可以走两次。完成任务最少需要多少机器人？

输入:第一行包含测试用例的数量 T。后面是 T 个测试用例。每个测试用例的第一行包含 N，即 Byteland 中的城市数量。城市编号为 0..N - 1。接下来的 N - 1 行包含对道路的描述。第i行包含两个整数ai和bi，表示有一条路连接编号为ai和bi的城市。

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

约束:1 <= T <= 20
1 <= N <= 10000
0 <= ai,bi < N

下面是我感到困惑的测试用例:

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
11 12

The correct answer is 2, but why?

Answer 1

请注意此处“相邻道路”的定义 - 您不是在寻找机器人仅通过每条道路一次的遍历。

根据定义，此图中有四个“终端道路”，6 10、5 13、2 14 和 7 9 - 它们不能位于序列的中间，因为它们只有一个相邻的道路。这是您可以使用两个机器人(从其中两个开始到另外两个结束)的第一个迹象。请注意，Byteland 几乎被分成两个子国家，只有 4 8 11 是唯一的连接道路，所以你不能让两个机器人从两半之间经过，这使得每个半部分由一个机器人修理是很自然的。

从那里开始，构建样本遍历(颜色 - 机器人，数字 - 序列)是相当微不足道的，当然有很多，因为你可以颠倒开始/结束并在两者之间打乱一些顺序

全部归功于 Graphviz和我的视觉皮层，但无论如何你都没有要求通用解决方案。