[Math] Maximum weight-matching in a tree

Question

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.

Answer 1

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!