是否存在O(n)时间复杂度的加权树最大匹配求解算法？

结论 #

完全可以通过树形动态规划实现O(n)时间复杂度的加权树最大匹配计算，递归实现也能达到该复杂度，无需担心效率问题。

动态规划思路 #

状态定义 #

对树中任意节点u，定义两个状态：

• dp[u][0]：以u为根的子树中，u未与任何子节点匹配时，该子树可获得的最大匹配权值和
• dp[u][1]：以u为根的子树中，u与某一个子节点匹配时，该子树可获得的最大匹配权值和

转移方程 #

首先任选一个节点作为整棵树的根（比如编号为1的节点），通过后序遍历的方式从叶子节点向上计算状态值：

1. dp[u][0]的计算
   因为u不与任何子节点匹配，所以每个子节点都可以自由选择自身匹配或不匹配的最优解，直接累加即可：

dp[u][0] = sum( max(dp[v][0], dp[v][1]) )

其中v为u的所有直接子节点。
2. dp[u][1]的计算
u需要和恰好一个子节点v匹配，此时被选中的v不能再和自身的子节点匹配，其余子节点仍可选择自身最优解。可以基于dp[u][0]的基础值做优化计算：

• 先计算所有子节点的max(dp[v][0], dp[v][1])总和（也就是dp[u][0]的值）
• 对每个子节点v，计算替换收益：(w(u,v) + dp[v][0]) - max(dp[v][0], dp[v][1])，其中w(u,v)是u和v连边的权值
• 取所有替换收益中的最大值，如果最大值为正，就加到dp[u][0]上得到dp[u][1]；如果最大值为负，说明u匹配任何子节点都不划算，dp[u][1]设为负无穷即可。

最终结果 #

整棵树的最大权匹配值为max(dp[root][0], dp[root][1])。

复杂度说明 #

每个节点仅会被遍历一次，所有节点的子节点处理总次数等于树的总边数n-1，因此整体时间复杂度为O(n)。递归实现仅在树为极端链状结构、深度超过语言默认递归栈限制时会出现栈溢出，此时改为迭代版后序遍历即可解决，不会改变时间复杂度。

内容的提问来源于stack exchange，提问作者456c526f