查找树中的路径/子路径，使得权重之和小于给定的整数

Question

给定具有n个节点（从1到n编号）和n-1个边的树。每条边都有两个整数，一个重量和一个增益，与之相关联。你也得到一个数字K.你可以从任何节点开始，你必须进行交易。在每次交易中，您都会损失等于边缘权重的金额，并获得等于边缘增益值的利润。您必须最大化利润，以便总损失的金额< = K

以下是原始问题的链接。相应的比赛现在结束了。

https://www.hackerrank.com/contests/gs-quantify-2017/challenges/profit-maximization

我所做的：

我建了一个递归方法通过考虑每个节点的路径的起始节点，然后通过考虑由无休止的后续节点的递归计算最大利润限制。

但显然这具有非常高的时间复杂性。

有没有更优雅更省时的方法？

Answer 1

这里有一个建议：

1. 选择靠近图形的中心（例如，通过反复修整的所有叶节点，并选择删除的最后一个节点）
2. 锻炼，如果解决方案的最佳盈利点使用该节点（不一定作为始节点 - 它可能只是在中间为好）
3. 制定出最佳的盈利，如果该解决方案采用依次对每个子树（即不使用所选择的节点）

要计算使用特定节点x的解决方案的利润，您可以使用DFS来计算达到每个节点的总权重和利润。

然后，对于x的每个子子树：

1. 构建从重量到利润有序映射（此映射重量增加来排序）
2. 删除任何条目，其中利润小于较早的利润（即更重，但给利润少点没有保持航线）

然后，您可以合并这些子树找到包含X的任何路线的最大利润：

1. 从子1的排序地图开始
2. 通过儿童1的地图向后迭代，然后向后通过儿童2的地图，以从儿童1开始到儿童2结束的路线中找到最高利润。
3. 合并为孩子1和2儿童的地图，然后重复孩子3,4,5 ...

注意步骤2和步骤3在条目数线性被合并。

如果存在较高的分支因子，则此合并步骤可能会变得太慢，在这种情况下，您可以通过始终合并两个最小子树而不是按顺序合并来提高效率。一个堆数据结构可以用来有效地告诉你哪两个最小。

有可能是一个更简单的解决方案，Hackerrank通常会在一段时间后发布社论，所以在未来值得重新检查您的问题链接。