# Dynamic Program for Tree based question

You are given a tree T where every node i has weight wi ≥ 0. Design a polynomial time algorithm to find the weight of the smallest vertex cover in T. For example, suppose in the following picture wa = 3, wb = 1, wc = 4, wd = 3, we = 6. Then, the minimum cost vertex cover has nodes a, b with weight 3 + 1 = 4.

In the question, the opt i am chosing is OPT(v,boolean) is a min weight vertex cover for subtree v and boolean means whether it contains v or not. What are the subproblems that are formed and how do I move ahead? any hint is helpful.

Taking y our idea we let $$OPT(v, 1)$$ to be equal to the minimum weight of a vertex cover of the subtree rooted in $$v$$ that includes $$v$$, and $$OPT(v, 0)$$ the one where $$v$$ is not included.
$$OPT(v,1)$$ means you the weight of that cover includes $$w(v)$$ and also that we have already dealt with edges that touch $$v$$, so all you need are MWVC for each of the subtrees of its children. So for each children $$u$$ of $$v$$, you take the minimum between $$OPT(u,0)$$ and $$OPT(u,1)$$, and you add that to $$OPT(v,1)$$. This can be done bottom-up.
$$OPT(v,0)$$ means you need to select every children $$u$$ of $$v$$, as otherwise the edge $$uv$$ wouldn't be covered. Thus, for every child $$u$$, you add $$OPT(u,1)$$ to $$OPT(v,0)$$.