O(n) 中加权树中的最大匹配

Question

是否有 O(n) 的算法来计算 weighted 树的最大匹配？

我只找到了未加权树或二部图的算法。我在将这些算法转换为树时遇到了一些麻烦。 我还用笔和纸发现，未加权树的算法不适用于加权树。 我认为递归地它需要的不仅仅是 O(n)，还有哪些选择？也许是动态规划？

非常感谢您的帮助。 谢谢:)

Answer 1

O(n)动态规划解法是选择任意一个节点作为根，然后在根匹配和根不匹配的情况下递归计算每个节点的子树中的最大匹配。

后序计算很简单（DFS）：节点的最大根不匹配匹配就是每个子树的最佳匹配的总和。一个节点的最大根匹配匹配是其一个子节点的根匹配到根不匹配子树的最佳匹配，加上其他子节点的最佳匹配。