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

Question

在O(n)中是否有计算加权树最大匹配的算法？

我只找到了非加权树或二分图的算法。我在将这些算法转换为树时遇到了一些困难。用笔和纸我也发现，非加权树的算法不适用于加权树。我认为递归需要比O(n)更多的时间，还有什么可供选择的？也许是动态规划？

我会很感激你的帮助。谢谢您:)

Answer 1

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

计算很容易在后置顺序(DFS)：一个节点的最大根不匹配匹配只是每个子树的最佳匹配的总和。一个节点的最大根匹配匹配是与其一个子节点的根不匹配子树匹配的根匹配的最佳匹配，并添加到其他子节点的最佳匹配中。