具有修改的树的动态规划

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,从root开始并检查孩子是否可以帮助完成它的顺序并相应地为该城市分配存储空间.但问题在于,孩子们也可以从父母那里完成订单,所以它正在制作循环循环.所以,它也没有帮助我.

3. 我最后的方法是考虑在答案本身上应用二进制搜索.由于答案可以介于(1,n)之间,因此可以在nLog(n)顺序中找到答案.但问题是,我无法想到在具有给定存储数量的城市中分配存储的最佳方式.

那么,多数民众赞成......我努力但却无法解决这个问题.任何帮助,将不胜感激.:)

注意:我不知道为什么他们这样复杂的问题陈述如此复杂.他们可以用更简单的方式轻松解释问题.结果我再也找不到网络上的这个问题了.我猜这是代码的某个地方.

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都为 false 或者任何邻居的need_more_storage为 true，则将当前节点的has_storage设置为 true；如果没有，则将has_storage设置为 false，如果只有一个邻近城市有存储，则将need_more_storage设置为 true；然后移动到一个未定义的邻居。
• 如果多个相邻节点未定义，则移动到其中任何一个未访问的节点。
• 如果没有未定义的相邻节点，则已到达最后一个节点；这始终是一个端点，因此将其has_storage设置为 true；算法现已完成。