<分区>
我有一棵以 1 为根的树。我可以删除任何节点的整个子树,并且可以在任何节点执行此操作。的时间。
假设我们执行了上面的操作k no。次。我们需要最大化 Total_weight - C*k,其中 C 是正常数。
节点的权重可以是正数也可以是负数。
例如-(1,1) (2,-5) (3,-5) 是节点,1-2 和 2-3 即 1,2 和 2,3 是相连的。令 c 为 1,所以在这种情况下,我们可以删除 2 的子树以最大化权重,即 1-1*1=0。
我可以尝试找出每个子树的权重并删除所有权重小于以 1 为根的树的权重的子树,但这不是最佳策略。我需要一个 O(V) 算法。
如果能帮助确定最佳算法,我们将不胜感激。