algorithm - 连接树中的节点

Question

一个假设性的问题。假设给了我一棵树 T 和 T 中的一对节点 (x, y) 列表。我被问到我最多可以使用 T 中的每条边同时连接多少对节点（将 x 与 y 连接） .

怎么会这样？

Answer 1

对于树来说，这不是 NP 难的。例如，您可以执行以下操作。

1. 任意扎根树。

2. 对于每个顶点 v，计算受限于 v 的子树的最优解。

3. 此外，对于每个 v，对于包括 v 的父边的每个路径 p，计算仅限于路径 p 之外的 v 的子树的最优解。

(2) 和 (3) 可以使用 v 的子树中较小问题的解决方案来计算。

查看步骤 1、2 和 3 并自己计算递归可能更容易，但只是为了给您一个想法，（2）可以通过取多个解决方案的最大值来计算：一个将解决方案相加v 的子级（即，在步骤 2 中为每个子级生成的解决方案的总和），一个用于包含 v 的每个路径加上其他子级的步骤 2 解决方案（这将基本上包括生成的一个或两个解决方案的总和在第 3 步中为 v 的孩子加上在第 2 步中为其他孩子生成的解的总和）。