codingexercise
Find the sub-tree with maximum  color difference in  a 2 colored tree
We define color difference as the magnitude of the number of vertices of one color minus the number of other color vertices where each number is a positive count.
Since it is not convenient to return all the subtrees and exhaust the search space,
We will keep track of minimum and maximum color difference of two subtrees and we will color 1 or –1 so that the equal number of both balance each other out.
When we perform a depth first search, we can find the maximum of any color by assigning  1 to that color. Since depth first traversal finds subtrees we have the maximum available for a sub tree.
When we invert the color, we can find the maximum of the opposite color with a similar depth first search.
During the depth first search for every node as the starting point, to find
1) max sum sub tree, we take a node if its value is greater than 0 => sum(parent) += max(0, sum(child))
2) min sum sub tree, we take a node if its value is lesser than 0 => sum(parent) += min(0, sum(child))
Thus for each node we have a color count array . Previously visited nodes already have this counted so this is a form of overlapping subproblems which we alleviate by memoization
After each depth first search we now have a color count array of a sub-tree for which we can find the maximum
When we get the maximum of both colors this way from the color count array, we know that the maximum color count difference is between this high number and nothing. Therefore, we have the color difference we are looking for.

int maxDiff(Node root, List<int> colors, int N)
{
   var counts = new List<int>();
   dfs(root, colors, ref counts);
   int max = counts.Max();
   colors.ForEach (x => Invert(x));
   dfs(root, colors, ref counts);
   max = Math.max(max, counts.Max());
   return max;
}