题解

思路

先从根结点 $1$ 出发进行深度优先遍历，记录每个结点的进入时刻 $tin_x$ 和退出时刻 $tout_x$。同一棵子树中的结点会在遍历序中形成连续区间，因此询问结点 $x$ 等价于询问区间 $[tin_x,tout_x]$ 中有多少种不同颜色。

这一转化也给出了三个自然的部分分算法。

当 $n\le 100$ 时，可以对每次询问直接遍历相应子树，并用集合统计颜色，单次询问至多访问 $n$ 个结点。

当所有结点颜色两两不同时，子树中的颜色数就是子树大小。一次树形遍历即可求出所有子树大小，随后每次询问直接回答。

当 $n,m\le 20000$ 时，可以把所有子树转成区间并使用莫队算法。移动区间左右端点时维护每种颜色的出现次数以及当前不同颜色数，便可回答所有询问。

做法

满分算法离线处理所有区间，并按照右端点从小到大排序。

从左到右扫描遍历序。设当前扫描到的位置为 $r$，该位置颜色为 $c$。若颜色 $c$ 之前最后一次出现于位置 $p$，就先在树状数组的 $p$ 处减一；再在 $r$ 处加一。这样，扫描到任意右端点后，树状数组中每种已出现颜色恰好只在它最后一次出现的位置保留一个 $1$。

对于右端点为 $r$ 的询问区间 $[l,r]$，颜色在该区间中出现，当且仅当它截至 $r$ 的最后一次出现位置不小于 $l$。因此区间内不同颜色数恰好等于树状数组在 $[l,r]$ 上的区间和。

将询问保留原编号，按右端点排序后依次扫描和回答，最后再按原顺序输出即可。

深度优先遍历采用显式栈实现，避免链形树造成递归栈过深。

复杂度

建立遍历序需要 $O(n)$ 时间。每个位置至多执行两次树状数组修改，每次询问执行一次区间查询，总时间复杂度为 $O((n+m)\log n)$，空间复杂度为 $O(n+m)$。