有限长度树中的最大子树总和

Question

我有一个树结构。任务是找到最大的sum/weight个路径节点，但是我只能移动n次。没关系，但是 "up"/"back" 不需要任何费用。我怎样才能做到这一点？

下面是我的代码，但问题是每个节点只能访问一次，所以它不起作用。

int mSum(Node* node, int mvLeft) {
    if (node == nullptr) { return 0; }
    if (mvLeft == 0) { return node->value; }
    mvLeft--;
    int sum = max(mSum(node->left, mvLeft), mSum(node->right, mvLeft));
    return node->value + max(sum, mSum(node->parent, mvLeft + 1));
}

这是示例图。节点上的数字代表到达它的成本。除了"back".
，每个节点只能被访问一次这里的 n 步限制是 3，我们也计算进入图形，所以正确的结果是 21，因为：2->8->11.
如果我们有 4 步的限制，结果将是 31：2->10->8->11
我的朋友试图用 DFS 来做，他说的对吗？最好的算法是什么？

Answer 1

好的答案是同时走多条路线。我的意思是我们可以使用 2 长度限制：

2 左 0 右
1 左 1 右
0 左 2 右

工作，但有点慢，代码:) 它的工作时间是 28 秒，而其他解决方案可以用 2 秒（10 个未知测试）

int mSum(Node* node, int mvLeft) {
    mvLeft--;
    if (mvLeft < 0) {
        return 0;
    }
    else if (mvLeft == 0) {
        return node->value;
    }

    if (node->left != nullptr && node->right != nullptr) {
        int max = 0;
        for (int i = 0; i <= mvLeft; i++) {
            max = Max(max, mSum(node->left, i) + mSum(node->right, mvLeft - i));
        }
        return max + node->value;
    }
    else if (node->left != nullptr) {
        return mSum(node->left, mvLeft) + node->value;
    }
    else if (node->right != nullptr) {
        return mSum(node->right, mvLeft) + node->value;
    }
    return node->value;
}

有限长度树中的最大子树总和

Max subtree sum in tree with limited length

graph-algorithm