$44)$ Let T be a tree with red and green vertices where each vertex v has its color preloaded in v$.$color and each

vertex w has the field w$.$count. For simplicity, let the root of T be red. Vertex v is the root of a maximum

green subtree if v is green, and its parent is red. The vertices in the green subtree rooted by such a v are all

vertices w that $($equal v or$)$ are descendants of v$,$ and the path from v to w only contains green vertices $($which

implies that w is also green$).$ Alternatively, these trees are the connected structures that remain if we remove

all read vertices and their connecting edges from T$.$

This exercise asks you to store, in the $($green$)$ root v of each maximum subtree, the number of $($green$)$

vertices in the tree. For specificity, this count should be stored in v$.$count.

Big Hint: these postorder DFS$-$based solutions are almost always more efficient if you use a code of the form:

procedure DFS$($;;v$)$

Initialize v as needed;

foreach child w in child$[$v$]$ do

DFS$($w$)$; $\{$ solve the same problem for each child one$-$by$-$one $\}$

update parent v with the solution just computed for child w

Of course, you also need to use the color of each vertex in this code

endfor

end$\_$DFS;

You are asked to write two different codes that perform this count as explained next.

$4\mathrm{.}1)$ Write a simple DFS that traverses T in a normal DF S process, and computes these counts of these green

vertices.

$4\mathrm{.}2)$ Write a procedure GFS$($v$)$ that only processes all of the vertices reachable from v on paths that only

contain green vertices. In addition, you will maintain a list Rist of all red vertices that GFS found, and $($by

definition$)$ refused to process. So you need additional code that repeatedly removes a red vertex from Rist,

examines its children, inserts the each red child in Rist $($to process later$),$ and runs GFS on the green

children. So this code processes T differently by running a restricted DFS that explores each maximum

green subtree of T$.$