一个假设性的问题。假设我得到了一棵树 T 和 T 中的一对节点 (x, y) 的列表。有人问我最多可以使用 T 中的每条边同时连接多少对节点(将 x 与 y 连接) .
怎么会这样呢？
最佳答案
这对树来说不是 NP 难的。例如，您可以执行以下操作。
任意根树。
对于每个顶点 v，计算限制在 v 的子树中的最优解。
此外，对于每个 v，对于包含 v 的父边的每个路径 p，计算除路径 p 之外限制在 v 的子树中的最优解。
(2) 和 (3) 可以使用 v 的子树中较小问题的解来计算。
查看步骤 1、2 和 3 并自己计算递归可能更容易，但只是为了给您一个想法，(2) 可以通过取几个解决方案中的最大值来计算:一个求和v 的子项的解决方案(即，第 2 步中为每个子项生成的解决方案的总和)，以及包含 v 的每个路径的一个解决方案加上其他子项的第 2 步解决方案(这基本上包括一个或在第 3 步中为 v 的 child 生成的两个解决方案，加上在第 2 步中为其他 child 生成的解决方案的总和)。
关于algorithm - 连接树中的节点，我们在Stack Overflow上找到一个类似的问题： https://stackoverflow.com/questions/4288447/