procedure Gcount(;;v);
if v.color == Green then v.count ← 1 else v.count ← 0 endif;
for each child w in Adj[v] do
Gcount(w);
v.count ← v.count + w.count
endfor
end_Gcount;
Tree-DP RPS
Example1: Let Val[1...n]Val[1...n]Val[1...n] contain n positive numbers, and let T be a fixed binary tree where each non-leaf has 2 children, and T has n leaves ℓ[1...n]\ell[1...n]ℓ[1...n] with ℓ[i]\ell[i]ℓ[i] containing the positive input value Val[i]Val[i]Val[i].
Problem: Let each internal vertex contain either a +++ operator or a ∗*∗ operator so that T is an arithmetic expression tree.
Present an RPS that computes the greatest possible value that T can have (which is when the internal operators are chosen to produce the largest possible value for their respective subtrees).
Example2: Let Val[1...n]Val[1...n]Val[1...n] contain n positive numbers, but have no tree T specified. Present an RPS that finds the largest possible value for any binary tree T where each vertex that is not a leaf has 2 children, and can contain a +++ or ∗*∗ operator as before, and T has the n leaves ℓ[1...n]\ell[1...n]ℓ[1...n], with ℓ[i]\ell[i]ℓ[i] storing the number Val[i]Val[i]Val[i].