在树中查找权重总和小于给定整数的路径/子路径

Question

给定一个具有n个节点(编号从1到n)和n-1条边的树。每条边都有两个与之关联的整数，一个权重和一个增益。你也会得到一个数字K，你可以从任何节点开始，你必须进行交易。在每笔交易中，你损失的金额等于边缘的权重，而赚取的利润等于边缘的增益值。你必须最大化利润，这样总的损失金额<=K

这里有一个指向原始问题的链接。相应的比赛现在结束了。

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

我做了什么：

我构建了一种递归方法，将每个节点视为路径的起始节点，然后通过考虑遵守约束的每个后续节点来递归计算最大利润。

但很明显，这具有非常高的时间复杂度。

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

Answer 1

这里有一个建议：

1. 选择图形中心附近的节点(例如，通过重复修剪所有叶节点并选择删除的最后一个节点)
2. 如果解决方案使用该节点(不一定作为开始节点-它也可能位于中间)，则
3. 计算最佳利润如果解决方案依次使用每个子树(即，不使用所选节点)，
4. 计算最佳利润

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

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

1. 构建了一个从权重到利润的排序地图(此地图应通过增加weight)
2. Remove任何利润小于较早利润的条目进行排序)

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

1. 从子节点1的已排序地图开始
2. 正向迭代子节点1的地图，向后迭代子节点2的地图，以查找从子节点1开始到子节点2的路径的最高利润。
3. 合并子节点1和子节点2的地图，然后对子节点3、4、5重复此操作...

请注意，步骤2和步骤3在要合并的条目数量上都是线性的。

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

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