Dynamic Programming on Tree: Forming up Subtrees with One Black Node

This problem is from Codeforces Round #263 (Div. 1) Problem B:

Problem Statement:
461B - Appleman and Tree

Solution:
The dynamic programming approach to this tree problem is quite interesting. The focus of the problem is to find the number of ways such that the subtrees formed have one and only one black node each. The idea behind the DP might not be that intuitive though, and in a sense its implementation is also not as straight forward, although its final implementation looks very simple.

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.