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.