SPOJ - Three-coloring of Binary Trees (THREECOL)

Problem Statement:
SPOJ - THREECOL

Summary:
Given a binary tree as specified (may not be balanced nor complete),  we can color the tree with three colors: red, green and blue, with the following restrictions:
1. A node and its child cannot have the same color.
2. For nodes with two children, the node and its children must all have different colors.
Find the maximum and minimum number possible of nodes colored in green.



Solution:
This problem nicely fits the dynamic programming paradigm, since it talks about trees. Let's first solve the part regarding the maximum number of green nodes. Define M(node, color) as the maximum number of green nodes possible if we start coloring the tree with node as the root, and color as its color. Then we have 3 cases:
1. If the current node has no children, then the maximum number of green nodes is either 1 or 0, 1 if the current node is colored green, and 0 otherwise.
2. If it has 1 child, then the child can be colored in exactly two ways, since it must have a different color from its parent. Hence M(node, color) = min { M(child, other_color) } for two choices of other_color.
3. If it has 2 child, then the children must each be colored with the two remaining colors. Then we have M(node, color) = min { M(first_child, other_color) + M(second_child, another_color) }, for each permutation of other_color and another_color.

We can solve all values of M(node, color) using recursion. Similarly, the minimum number of possible green nodes can be solved in a symmetrical fashion.