THREECOL in Python

My approach is dfs with memoization. First, generate a tree from given input, then run the recursive function (with cache) on the tree. Let's define the function f(isGreen,node) as the {minimum|maximum} number of green color nodes in the subtree below @node and @node itself, when the @node have color {green if @isGreen=True, red or blue otherwise}.

Now, we will consider the case we want the maximum number of green nodes.

If the number of children for @node is 0, f(isGreen,node) is defined as follows:

	if @isGreen==True:
		f(isGreen,node) = 1
	else:
		f(isGreen,node) = 0

If the number of children for @node is 1, f(isGreen,node) is defined as follows:

	if @isGreen==True:
		f(isGreen,node) = f(False,@node's child) + 1
	else:
		f(isGreen,node) = max(f(True,@node's child),f(False,@node's child))

If the number of children for @node is 2, f(isGreen,node) is defined as follows:

	if @isGreen==True:
		f(isGreen,node) = f(False,@node's 1st child) + f(False,@node's 2nd child) + 1
	else:
		A = f(True,@node's 1st child) + f(False,@node's 2nd child)
		B = f(False,@node's 1st child) + f(True,@node's 2nd child)
		f(isGreen,node) = max(A,B)

For the case we want the minimum number of green nodes, just change max() to min().

I didn't do any optimizations. I think our approach is O(N*2), and it should run within the time limit.
Can you show me your code for checking overhead?

I checked your code. I fixed following things and made it accepted.

1. I think your code does not insert the current state into @cache.
2. Since dictionary datastructure takes O(log n) time for {insertion|lookup},
   I changed @cache into 2D array which takes O(1) for lookup.
   I added one int variable into Node class to represent nodeid.
3. I added psyco.full().

These fixes made your code run in 6.77secs.
Another big difference between your code and my code was tree datastructure.
Your code used reference to child node whereas my code used 2D adjacent list.
When I changed it into 2D adjacent list, your code run in 1.73secs.

In my opinion, creating and accessing class objects take much longer time than 2D list. I checked running time of constructing tree and calc() function using the official dataset. In the experiment, 2D list runs about 3 times faster than class object for {tree construction|calc()}.

For the tree construction, generating Tree class and Node class which have 3 or more variables are clearly slower than 2D list. However, I still don't know why calc() also takes much longer time by using class objects.

By the way, this problem could be solved without psyco by using 2D adjacency list.