algorithm - 修改树上的动态规划

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。而且我也不确定这是否是最佳的。从上面的问题我可以确保 叶子肯定有 1 个存储空间。 我在想 DP，从根开始，检查 child 是否可以帮助完成它的订单，并相应地为那个城市分配存储空间，叶子上有底壳。但问题是， children 也可以完成 parent 的订单，所以它形成了循环。所以，它对我也没有帮助。

3. 我考虑的最后一种方法是对答案本身应用二分搜索。由于答案可能位于 (1,n) 之间，因此可以按 nLog(n) 顺序找到答案。但同样的问题是，我想不出在具有给定存储数量的城市中分配存储的最佳方式。

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

注意:我不知道他们为什么把问题陈述得这么复杂。他们可以很容易地以更简单的方式解释问题。结果我在网上再也找不到这个问题了。我猜它在 codeforces 的某个地方。

Answer 1

关于该图需要注意的重要一点是，有 n 个城市和 n-1 条道路，并且所有城市都是可达的；这意味着:

• 没有循环路径。
• 至少有 2 个单独连接的城市(端点)。

每个城市都有两种可能性；要么:

• 该城市有一个存储设施，另一个存储设施距离最多 2 个城市。
• 该城市没有存储设施，并且与至少两个拥有存储设施的城市相连。

这也意味着一个单连接的城市(道路的终点)总是有一个存储设施，而一串双连接的城市应该(最佳)交替地有一个存储设施或没有，这将给我们决定在何处放置存储设施时的起点。

^{蓝色:当前节点；绿色:存储；橙色:无存储； +:需要另一个有存储空间的邻居； ?: 已访问但尚未解决}

这给了我们以下算法:

• 先找到一个终点:从任何城市开始，向任何方向移动直到你来到一个单独连接的城市。
• 在单连接城市放置一个存储设施，然后返回之前的城市，并将通往您来自的城市的道路标记为参观了。
• 如果这个城市只有另一条未经过的道路，则沿着人迹罕至的道路，在有或没有的情况下留下相邻城市的踪迹存储设施。
• 如果你来到一个有不止一条无人踏足的道路的城市，等待决定是否放置存储设施并采取任何人迹罕至的道路；稍后当你回到这个城市时，它已经只有一条人迹罕至的路，你会知道有没有已经走过的路访问邻近城市需要这个城市有一个存储设施。
• 一直这样做，直到您最终到达一个没有未经过的道路的城市；这意味着您已经浏览了整个图表。

这基本上是一个“遍历所有道路并再次回溯”的算法，因此访问的节点数为 2×N，复杂度为线性或 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为true，则设置当前节点的has_storage为true；如果没有，则将has_storage设置为false，如果只有一个相邻城市有存储，则将needs_more_storage设置为true；然后移动到一个未定义的邻居。
• 如果几个相邻节点未定义，则移动到其中任何一个未访问过的节点。
• 如果没有一个相邻节点是未定义的，你就到达了最后一个节点；这始终是一个终点，因此将其 has_storage 设置为 true；该算法现已完成。