连接树中的节点

Question

作为一个假设问题，假设我得到一棵树 T 和 T 中的一对节点 (x, y) 的列表。我被问到可以使用每个节点同时连接多少对节点（将 x 与 y 连接） T 中的边缘最多一次。

如何做到这一点？

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 中为其他子级生成的解决方案的总和）。