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

Question

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

表示节点 i 的值

以下操作可以执行任意次数（包括零次）：

1.choose 树中仍然存在的任何节点，并删除该节点的整个子树，包括它自己。

2.Let将利润定义为树中当前存在的所有节点的值之和减去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

这个想法是解析树，看看哪个子树可以被移除，这样利润会比其初始状态增加。在删除任何内容之前对每个节点进行此分析。然后，删除增加最多利润的子树。我们可以分两次完成：

1) 对树进行depth-first遍历（先离开，然后慢慢回到根），计算每个节点的利润增益为G(i)=-A(i)+G(j)+G(k)+...，其中i是当前节点，j,k,...是children。换句话说，如果我们删除当前节点，则利润增益是增加的值。

在同一次遍历中，还要计算节点的最大利润增益及其children。这将告诉我们是删除一个节点更有利可图，还是删除该节点的子树更有利可图。我们将最大利润收益计算为 M(i) = max(G(i),M(j),M(k),...)，其中 i,j,k,... 定义如上。如果 child 不存在，只需将其从 max 等式中删除即可。

2) 对树进行 breadth-first 遍历，如果 G(i) == M(i) 和 G(i) >= X.[=20=，我们删除节点 i（及其子树） ]

def compute_gain(node):
    map(compute_gain, node.children)
    node.gain = -node.value + sum([c.gain for c in node.children])
    node.max_gain = max(node.gain, max([c.max_gain for c in node.children]))

def prune_tree(node):
    if node.gain >= X and node.max_gain == node.gain:
        k += 1
        return False
    node.children = [c for c in node.children if prune_tree(c) == True]

Answer 2

对此有一个简单的递归算法。您可以对一棵树执行的最有利可图的修剪是对其所有直接子树执行最有利可图的修剪，或者只是修剪整棵树。这可以直接翻译成代码。

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

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

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

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

How to maximize the weight of a tree by removing subtrees

binary-tree

subtree