is there an algorithm in O(n) to calculate the maximum matching for a weighted Tree?

I only found algorithms for unweighted trees or bipartite graphs. I have some trouble converting these algorithms for trees. With pen and paper i also found out, that the algorithm for unweighted trees does not work for weighted trees. I think recursively it would take more than O(n), what are the alternatives? Dynamic Programming maybe?

Help would be much appreciated. Thank you :)

CodePudding user response：

The O(n) dynamic programming solution is to choose any node as the root, and then recursively calculate the maximum matching in each node's subtree in the root-matched and root-unmatched conditions.

The calculation is easy in postorder (DFS): The max root-unmatched matching for a node is just the sum of the best matchings for each child subtree. The max root-matched matching for a node is the best matching with the root matched to the root-unmatched subtree for one of its children, added to the best matchings from the other children.