Q:

Algorithmic Puzzle: Distinct nodes in a subtree

I am trying to solve this question:

You are given a rooted tree consisting of n nodes. The nodes are
  numbered 1,2,…,n, and node 1 is the root. Each node has a color.
Your task is to determine for each node the number of distinct colors
  in the subtree of the node.

The brute force solution is to store a set for each node and them cumulatively merge them in a depth first search. That would run in n^2, not very efficient. 
How do I solve this (and the same class of problems) efficiently?

A:

For each node,

Recursively traverse the left and right nodes.
Have each call return a HashSet of color.
At each node, merge the left child set, the right child set .
Update the count for the current node in a HashMap.
Add the color of current node and return the set.

Sample C# code:
public Dictionary<Node, Integer> distinctColorCount = new ...

public HashSet<Color> GetUniqueColorsTill (TreeNode t) {
    // If null node, return empty set.
    if (t == null) return new HashSet<Color>();

    // If we reached here, we are at a non-null node.
    // First get the set from its left child.
    var lSet = GetUniqueColorsTill(t.Left);

    // Second get the set from its right child.
    var rSet = GetUniqueColorsTill(t.Right);

    // Now, merge the two sets.
    // Can be a little clever here. Merge smaller set to bigger set.
    var returnSet = rSet;
    returnSet.AddAll(lSet);

    // Put the count for this node in the dictionary.
    distinctColorCount[t] = returnSet.Count;    

    // Finally, add the color of current node and return.
    returnSet.Add(t.Color);

    return returnSet;
}

You can figure out the complexity exactly as @user58697 commented on your question using the Master Theorem. This is another answer from me written long time ago that explains Master Theorem, if you need a refresher.
c#

