我得到一棵(不一定是二叉)树，节点上有整数(正/负)标签，并且必须找到使树中标签之和最大化的二 fork 树。我想到了动态规划方法——我定义了 f(u)，它返回以 u 为根的所有二叉树的最大总和，并通过选择 v、w 来计算 f(u)，使得 v、w 是 u 的子节点，并且它们最大化对所有 u 的 child 对求和 (f(v)+f(w))，然后 f(u) = label(u) + f(v) + f(w)。 f 可以在典型的动态规划方法中从叶子向上计算。我的问题是:
(1) 有没有更有效的方法？ (2) 成本最高的步骤似乎是在你的所有 child 对中找到最大值——如果你有 n 个 child ，成本是 O(n^2)，但我认为对于整棵树来说它小于 O(| E|^2)，是真的吗？我怎样才能更严格地计算成本？
谢谢。
最佳答案
如果节点 U 有 n 个子节点，您可以通过简单地取最大化 f(V) 和 f(W) 的子节点来找到使 f(U) 最大化的一对子节点 V,W。您不需要实际检查每一对。您可以在 O(2n) = O(n) 中轻松做到这一点，而不需要 O(n2).
例如，如果子节点的 f 值是 { 6, 5, 2, 12, 8 }，那么您只需要两个最大值，即 8 和 12。您不需要实际检查每一对值并显式添加它们。
(注意:如果任一选定节点的 f 值为负，那么您应该将其删除。您的二叉树是否允许只有一个子节点的内部节点？)
关于algorithm - 查找给定(不一定是二叉)树的最大和二 fork 树，我们在Stack Overflow上找到一个类似的问题： https://stackoverflow.com/questions/41705354/