如何通过删除子树来最大化树的权重

Question

有一棵有N个节点（编号1到N）的根树。节点“ 1”是根。每个节点都有一个值；让我们用A（i）表示节点i的值。

可以多次执行以下操作（包括零次）：

1.选择树中仍然存在的任何节点，并删除该节点的整个子树，包括它本身。

2.让我们将利润定义为树中当前存在的所有节点的值之和减去X？k，其中k表示执行此操作的次数。找到最大可能的利润。

我们如何在这里计算“ k”值？（意味着删除时间节点数以获取最佳利润）

例：-

3(number of nodes,N) ,

5(X)

1 -5 -10 (Values of corresponding nodes)

(edge(s) from 'x'->'y')

1 2

2 3

Output: -4

We remove the sub-tree of node : 2'.

Now,value of our tree is: 1.

Finals answer:- 1-(x)*k,
(k=1); as we have performed the operation of removing the sub-tree only '1' time 
:  1-(5)*1= -4.

注意：没有给出树应该是二进制的，它也可以是普通树。

Answer 1

为此有一个简单的递归算法。您可以在树上执行的最有利的修剪是在其所有直接子树上执行最有利的修剪，或者仅修剪整棵树。这可以直接转换为代码。

假设树已被处理成一个数据结构，其中每个节点都有一个value代表节点值的children属性和一个存储节点子节点列表的属性，以下Python函数将计算最大利润：

def max_profit(node):
    return max(
        -X,
        node.value + sum(map(max_profit, node.children)))

max调用中的两个选项代表选择修剪整棵树的根，还是保留根并处理子树。