算法难题：子树中的不同节点

我正在尝试解决这个问题：

您将获得由n个节点组成的根树。节点是   编号为1,2，…，n，节点1为根。每个节点都有一种颜色。      您的任务是为每个节点确定不同颜色的数量   在节点的子树中。

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.

如何有效解决此问题（以及同类问题）？