连接树中的节点
作为一个假设问题，假设给定一棵树 T 和 T 中的一对节点 (x, y) 列表。我被问到使用每条边可以同时连接多少对节点（将 x 与 y 连接）在 T 中最多一次。
一个人会怎样做呢？
As a hypothetical question, say I'm given a tree T and a list of pair of nodes (x, y) in T. I'm asked how many of the pairs I can connect simultaneously (connect x with y) using each edge in T at most once.
How would one do that?
如果你对这篇内容有疑问，欢迎到本站社区发帖提问 参与讨论，获取更多帮助，或者扫码二维码加入 Web 技术交流群。
绑定邮箱获取回复消息
由于您还没有绑定你的真实邮箱，如果其他用户或者作者回复了您的评论，将不能在第一时间通知您！
发布评论
评论（1）
对于树来说这不是 NP 困难的。例如，您可以执行以下操作。
任意给树生根。
对于每个顶点 v，计算仅限于 v 子树的最优解。
此外，对于每个 v，对于包含 v 父边的每个路径 p，计算仅限于除路径 p 之外的 v 子树的最优解。
(2) 和 (3) 可以使用 v 子树内较小问题的解来计算。
查看步骤 1、2 和 3，并自己计算出递归式可能更容易，但只是为了给您一个想法，可以通过取多个解的最大值来计算 (2)：将v 的子级（即，步骤 2 中为每个子级生成的解决方案的总和），以及包含 v 的每条路径加上其他子级的步骤 2 解决方案（这基本上包括生成的一个或两个解决方案的总和）在步骤 3 中为 v 的子项加上步骤 2 中为其他子项生成的解的总和）。
It isn't NP-hard for trees. You can do the following, for example.
Root the tree arbitrarily.
For each vertex v, compute the optimal solution that is confined to v's subtree.
Additionally, for each v, for each path p that includes v's parent edge, compute the optimal solution that is confined to v's subtree except for path p.
(2) and (3) can be computed using the solutions to the smaller problems within v's subtree.
It's probably easier to look at steps 1, 2, and 3, and figure out the recurrence yourself, but just to give you an idea, (2) can be computed by taking the maximum of several solutions: one that sums the solutions for the children of v (i.e., the sum of the solutions produced in step 2 for each child), and one for each path that includes v plus the step 2 solutions for the other children (this will essentially include the sum of one or two solutions produced in step 3 for v's children, plus the sum of the solutions produced in step 2 for the other children).