For each node, run a DFS to collect all colors in its subtree, then count distinct values. This is per node, so total. Too slow. Alternatively, maintain a set per node and merge child sets after processing them. If you merge in arbitrary order, you hit the chain case.
Small-to-large merging fixes this. By always merging the smaller set into the larger one, you guarantee total operations across all merges in the tree.