Find Maximum-Matching in a tree $T(V, E)$ in $O(V)$ It's a question from a previous exam that I'm trying to solve with no success.


Suggest a Dynamic-Programming algorithm  for the following problem:
Input: indirected tree $T(V, E)$.
Output: a Maximum-Matching in the tree.
Any node have additional $O(1)$ memory.
Required Big-O: $O(|V|)$.

I don't have a clue how to start.
Can you kindly give me some hints to solve it?
Thanks in advance.
 A: One thing that helps is to root the tree, simply by assigning an arbitrary vertex $r$ as the root of $T$.
In this case, dynamic programming on trees often work in a bottom-up manner (or post-order traversal of the vertices).
That is, say you have a function $f : V \rightarrow \mathbb{N}$ where $f(v)$ is the score of the maximum matching of the subtree rooted at $v$.  The function $f(v)$ relies on the values of $f(v_1), f(v_2), \ldots, f(v_k)$, where $v_1, \ldots, v_k$ are the children of $v$ in $T$.
When you work up your way to $f(r)$, you are done.
In the problem of max matching, there are two cases for a given $v$.  Either you include exactly one edge joining $v$ and one of its children, or you include no such edge.
So actually you might need to pieces of information for each $v$.
Call $g(v, 0)$ the score of a max matching of the tree rooted at $v$ that includes no edge between $v$ and one of its children.
And call $g(v, 1)$ the score when $v$ includes one such edge.
Now, given $g(v_i, 0)$ and $g(v_i, 1)$ for every child $v_i$ of $v$, can you compute $g(v, 0)$ and $g(v, 1)$.  Can you compute $f(v)$ from that ?
