A variant of the vertex cover problem on trees
Define $f(v,r,s)$ to be the minimum size of a multiset $S$ that covers the entire tree rooted at $v$, such that $S$ contains exactly $r$ copies of $v$'s parent and exactly $s$ copies of $v$.

Then you can express $f(v,r,s)$ in terms of the values $f(w_i,s,t_i)$, where the $w_i$'s are the children of $v$.  If the tree is a binary tree, there are only $9=O(1)$ cases you need to consider and at most $2\times 3=O(1)$ terms in the recursive expression for $f(v,r,s)$.  The case analysis gets a bit ugly, but it's all $O(1)$.

Therefore, you get a $O(n)$ time algorithm for this problem, if the tree is guaranteed to be a binary tree.  I don't know what happens for general trees of unlimited degree.