Question $1$: Consider a rooted tree that has n vertices. A positive weight is associated with every vertex. We want to select a subset of independent vertices so that the sum of weights of the selected vertices is the maximum. Note that, a set of vertices are independent if no pair of vertices in this set share an edge between them. $($hint: use dynamic programming, say fy$($u$)$ and fn$($u$)$ are the maximum weight of the independent set for the subtree rooted at node u when u is selected, and not selected, respectively. Now write optimal substructure equation for both fy$($u$)$ and fn$($u$)$ using the optimal

solution of u$$s children.$)$

Question $2$: For the problem in Question $1,$ now assume that weight value of all the vertices is exactly $1.$Now use a greedy algorithm to solve this problem.