$3.$

a$)$ Let T $=($V$,$ E$)$ be a tree with the child lists Adj$[$v$],$ which list v$$s children, and where each vertex v has a preloaded color

v$.$color that equals r or g$,$ and a field v$.$count.

Present a linear time DFS that stores, in each v$.$count, the largest number of g$-$colored vertices on any ONE path that starts

at v$,$ and runs down to a tree leaf. So for all paths that start at v$,$ you want to use the path with the largest g$-$count. This

count includes v if v$.$color $=$ g$.$

b$)$ Let D $=($V$,$ E$)$ be a DAG. Present a linear time $($i$.$e$.(|$V $|+|$E$|))-$time DFS that stores, in each v$.$count, the largest

number of g$-$colored vertices on any ONE path that starts at v$,$ and runs down to a tree leaf. So for all paths that start at v$,$

you want to use the path with the largest g$-$count. This count includes v if v$.$color $=$ g$.$

Comments: You need a driver to ensure that all leaf$-$like vertices are processed. You are free to give v additional fields if needed.

You cannot afford to process a vertex repeatedly. Your coding will be simpler of you steal Tarjan$$s $$I don$$t care where I start

idea$$ as used in the driver for his postorder reverse topological sort.

c$)$ Let D $=($V$,$ E$)$ be DAG. Present a linear time $($i$.$e$.(|$V $|+|$E$|))-$time DFS that stores, in each v$.$count, the largest number

of consecutive g$-$colored vertices on any path where the path $($but not nessarily that sequence of consecutive g$-$vertices$)$ starts

at v and runs down to a leaf$-$like vertex in D$.$ Comments: Reread part b$$s comments above. They all apply here as well. In

addition, you probably need to compute two counts for each v$.$ One is the solution v$.$count. The other is v$.$fromme, which

counts the largest number of consecutive g vertices on any DAG path that descends from v and where the v$.$fromme count of

consecutive green vertices must begin with v$.$color. So v$.$fromme must be zero if v$.$color $=$ r$.$