如何通过删除子树来最大化树的权重 [英] How to maximize the weight of a tree by removing subtrees

问题描述

有一棵有N个节点(编号1到N)的根树；节点"1"是根.每个节点都有一个值；让我们用A(i)表示节点i的值.

There is a rooted tree with N nodes (numbered 1 through N); node '1' is the root. Each node has a value; let's denote the value of node i by A(i).

以下操作可以执行任意次(包括零次):

The following operation(s) can be performed any number of times (including zero):

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

1.choose any node which still exists in the tree and remove the whole sub- tree of this node including itself.

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

2.Let's define the profit as the sum of values of all nodes which currently exist in the tree minus X⋅k, where k denotes the number of times this operation was performed. Find the maximum possible profit.

我们如何在此处计算"k"值?(意味着删除时间节点数以获取最佳利润)

How can we calculate 'k' value here?(means no. of time node is deleted to give optimum profit)

示例:-

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.

注意:并不是说树应该是二叉树，它也可以是普通树.

推荐答案

有一个简单的递归算法.可以对树执行的最有利的修剪操作是对其所有直接子树执行最有利的修剪操作，或者仅修剪整棵树.可以直接将其翻译为代码.

There's a straightforward recursive algorithm for this. The most profitable pruning you can perform on a tree is either to perform the most profitable pruning on all of its direct subtrees, or to just prune away the whole tree. This can be translated directly to code.

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

Assuming the tree has been processed into a data structure where every node has a value attribute representing the node's value and a children attribute storing a list of the node's child nodes, the following Python function would compute the max profit:

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

具有max调用中的两个选项，表示可以选择修剪整棵树的根，还是保留根并处理子树.

with the two options in the max call representing the choice to either prune the whole tree away at the root, or to keep the root and process the subtrees.

这篇关于如何通过删除子树来最大化树的权重的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！