Ex$.4\mathrm{.}26$ Dynamic Programming, dimension lifting

The green and blue tree optimization problem is this. The data is an arbitrary tree $\backslash ($ T $\backslash )$ where each vertex $\backslash ($ v $\backslash )$ in $\backslash ($ T $\backslash )$ has a preloaded number v$.$dat, and a blank field v$.$color. A tree is legally colored if each $.$color field is assigned one of the two colors green or blue, and no tree edge in $\backslash ($ T $\backslash )$ connects a blue parent to a blue child. All of the vertices could be green, but a blue parent can only have green children.

The value of a legally colored tree is the sum of the $.$dat numbers for the blue vertices. We can express this as

$\backslash [$

$\backslash$operatorname$\{$val$\}($T$)=\backslash$sum$\_\{$v $\backslash$text $\{$ in $\}$ T$,\backslash$text $\{$ v$.$color$=$blue $\}\}$ v $.$ d a t $.$

$\backslash ]$

a$)$Without peeking into the text: write a recursive dynamic programming specification for the problem of finding largest value that can be computed for $\backslash (\backslash$operatorname$\{$val$\}($T$)\backslash )$ when the colorings are required to be legal.

BIG hint: Write two recursive specifications. One is for $\backslash (\backslash$operatorname$\{$Blest$\}($w$)\backslash )$ which gives the best value for the best legal coloring for the subtree rooted by $\backslash ($ w $\backslash )$ when $\backslash ($ w $\backslash )$ is colored blue, and the other defines $\backslash (\backslash$operatorname$\{$Grest$\}($w$)\backslash )$ which does the same when $\backslash ($ w $\backslash )$ is colored green. For convience combined with high expressiveness, you might want to use expressions such as

$\backslash [$

$\backslash$sum$\_\{$v $\backslash$text $\{$ in $\}\backslash$operatorname$\{$Adj$\}[$w$]\}$

$\backslash ]$

which denotes a sum over all children $\backslash ($ v $\backslash )$ of $\backslash ($ w $\backslash ).$

b$)$ How would you store the solutions to already computed subproblems to ensure that the computation is efficient? That is$,$ to make the code efficient, you need to use a lookup data structure. So the question is: how should that be done?

Curiously, there is more than one reasonable answer to this question.

c$)$ Briefly explain a reasonable way to save the coloring decisions for the vertices that give the best answer.

d$)$ Present an efficient pseudocode that computes and prints the numerical solution for this problem, and also prints out the vertex names and colors. It suffices to write "print $\backslash (($v$)\backslash )"$ or "print $\backslash (($v $.$ n a m e$)\backslash )"$ to print the name of vertex $\backslash ($ v $\backslash ).$