修改树的动态规划

Question

最近我在树上读了一个问题但是我发现在解决这个问题上遇到困难。这里是问题：

有国家具有n个城市（2到10^5）和第（n-1）的双向道路，使得这是可能的任何一对城市之间旅行。我们有1个魔卡车可城市之间旅行，但它会采取1个单位的时间（如果它的加载）和0单位时间（如果没有加载）在相邻城市之间旅行，并产品可在持有1个单位的产品。

现在，你可以在需要谁究竟2个单位的产品，不能等待超过2个单位时间任何城市的客户。

现在的问题是，我们要尽量减少给定的限制储存总数：

1. 一个城市不能有一个以上的存储。
2. 存储只能存储1个单位的产品。

指定国家的储存所以您可以按时填写至少第一个订单。鉴于订单可以放在任何城市。

时间限制：1秒

我曾尝试：

1. 我能想到的最糟糕的做法是蛮力。尝试在每个城市放置存储（2^n种可能性），并检查每个城市订单是否可以在邻近城市的帮助下完成。但是时间复杂度会是（n * 2^n）。所以根本无法工作。

2. 我想到的第二种方法是在树上以某种方式使用DP。而且我也不确定这是否是最佳选择。从上面的问题我可以确保叶子应该有一个存储肯定。我想DP是这样的，从根开始，检查孩子是否可以帮助实现它的顺序并相应地为该城市分配存储空间，以叶子为基础的情况。但问题在这里，孩子们也可以完成父母的命令，所以它是循环循环。所以，它也没有帮助我。

3. 最后一种方法我正在考虑在答案上应用二分查找。由于答案可能在（1，n）之间，因此可以按照nLog（n）的顺序找到答案。但问题是，我想不出一种最佳的方式来分配具有给定数量的存储的城市的存储。

所以，这就是它..我努力尝试，但无法解决这个问题。任何帮助，将不胜感激。 :)

注意：我不知道他们为什么会让问题陈述如此复杂。他们可以用更简单的方式轻松解释问题。导致我无法再在网上找到这个问题。这是我猜想的代码的某处。

Answer 1

关于图表需要注意的重要一点是，有n个城市和n-1条道路，所有城市都可到达;这意味着：

• 没有循环路径。
• 至少有2个单独连接的城市（终点）。

每个城市都有两种可能性;要么是：

• 城市有一个存储设施，另一个存储设施是最多2个城市。
• 这个城市没有储存设施，并且连接到至少两个有储存设施的城市。

这也意味着，单连接城市（道路的终点），总有一个储存设施，和双连接城市的字符串应该（最佳）交替有一个储存设施或没有，这在决定将储存设施放在哪里时，将给我们一个起点。

^{蓝色：当前节点;绿色：存储;橙色：无存储; +：需要另一个有存储空间的邻居; ？：走访但尚未解决}

这给了我们如下算法：

• 先找到一个终点：在任何一个城市开始，任何方向移动 直到你来到一个单连接市。
• 在单独连接的城市中放置一个储存设施，然后返回到前一个城市的 ，并标记出去的城市之路为 参观。
• 如果这个城市只有一条其他未访问的道路，沿 未访问的道路行驶，留下相邻城市的小道，有或没有 的存储设施。
• 如果您来到一个有多个未访问道路的城市，请等待 决定是否要放置一个存储设施，并采取任何 未访问道路;后来当你回到这个城市，它只有一个未访问的道路，你会知道是否已经有 访问邻近的城市需要这个城市有一个存储 设施。
• 做到这一点，直到你最终在一个没有未经探访过的道路的城市;这个 意味着你已经浏览了整个图表。

这基本上是一个“遍历全部道路和再次回溯”算法，所以访问节点的数量为2个，其复杂度为线性或O（N）。

---

值得一提的是，在这城市的访问顺序不会改变结果，即存储设施的数量，但它可能会改变他们的一些位置。考虑这两个解决方案的4个城市：

S -/- S - S (solved left to right) 
S - S -/- S (solved right to left) 

---

移动更接近实际的代码，让我们看看做什么，一旦你已经确定了终点。该图由诸如例如这样的：

NODE "city" C1 
- neighbours: [C2, C4, C7] 
- has_storage: undefined   <- at first; will be set to true/false 
- needs_more_storage: true/false <- we'll add this property as we go 
- visited: true/false    <- we'll add this property as we go 

我们开始在终点，然后针对每个节点，我们将：

• 标记为访问节点。
• 看看邻居节点：如果你发现只有一个是不确定的，确定has_storage当前节点：如果所有的邻居 has_storage都是假的或任何邻国 needs_more_storage是真实的，设置当前节点的 has_storage为true;如果不是，则将 has_storage设置为false，并将 needs_more_storage设置为true，如果只有一个相邻城市存储;然后移动到一个未定义的邻居。
• 如果几个相邻节点未定义，请移至其中任何未访问的节点。
• 如果没有相邻节点未定义，则您已到达最后一个节点;这总是一个终点，因此将其 has_storage设置为true;该算法现在已经完成。