A solution built on these lines passed all test cases:

Perform a depth-first search preprocessing step on the tree starting at the root (which is actually specified in the input). When first encountering a node, create a colour set that will contain all the colours in the subtree rooted at that node, add the colour of the node to this set, then process each child of the node.

Whenever you finish processing a node:

• Record the size of its colour set - this record will be used for answering queries.
• If its colour set is bigger than its parent's colour set so far, switch the two sets, because it's more efficient to add elements from a smaller set to a larger one than vice versa.
• Add each element in the child's colour set to the parent's colour set.