# Maximum weight-matching in a tree

I'm practicing solving algorithm problems and can't manage with this problem:

We are given a tree with $n$ vertices by the list of $n-1$ tuples: $\langle a_i, b_i, w_i\rangle$, where $a_i\neq b_i, \ 1\le a_i, b_i \le n, \ 1\le w_i\le 1000, \ 2\le n\le 300000$, which means that vertex with number $a_i$ is connected with $b_i$ and this edge has weight $w_i$. The problem is to find maximum weight-matching in this tree.

For example tree:

n = 7

1 - 3; 2 (which means that vertices 1,2 are connected with an edge with weight $2$)

3 - 2; 1

2 - 4; 5

2 - 5; 7

3 - 6; 10

6 - 7; 1

The answer is $17$ (we take edges with weights: $10$ and $7$).

I have heard that this problem is in general very difficult, but I suspect that the fact that the graph we are given is a tree, is a great convenience. But still don't know how to use it.

-

You can use dynamic programming to find an efficient ($O(n)$) solution for a tree. The standard matching algorithms (finding a maximum weight matching is not that hard) will give solutions too, even if they're less efficient.

-
Right! Easier than I thought. Thank you very much. – xan Mar 4 '13 at 16:45

Hint:

Consider a rooted tree and let $\mathcal{T}$ be the set of all its subtrees. Let

• $f : \mathcal{T} \to \mathbb{R}$ be a function that for a given tree $T$ returns the cost of any maximum-weight matching in $T$,
• $g : \mathcal{T} \to \mathbb{R}$ be a function that for a givent tree $T$ returns the cost of maximum-weight matching in $T$ that does not use the root.

Then

\begin{align} g(T) &= \sum_{C \text{ child of } T} f(C), \\ f(T) &= g(T) + \max\left(0,\quad \max_{C \text{ child of } T} w_{\mathrm{root},C} + g(C) - f(C) \right). \end{align}

Good luck!

-
Thank you very much :-) – xan Mar 4 '13 at 16:46