问题：

有一类树上问题形式如下：

给定一棵树，大小为 ，点有颜色，分别记为 。对于树上的每个子树，求子树中不同颜色数量。

常见的做法有树上启发式合并和莫队算法。

dsu on tree

树上启发式合并一般可以用数组实现或者使用 set。

数组

使用计数数组维护颜色出现的数量，由于不能在每个节点上都开一个数组，因此需要将所有数据都记到这个数组上。

对于这道题，算法流程是：

• 计算每个子树的大小，并且称
  • 重子节点表示其子节点中子树最大的子结点，若有多个子树最大的子结点，任取其一；若无子节点，则亦无重子节点；
  • 轻子节点表示剩余的子结点；
  • 重边为节点到其重子节点上的边；
  • 轻边为重边以外的边；
• 在树上进行 DFS（ 函数），对于每个节点：
  1. 将 应用到所有轻子节点上，然后撤销其对计数数组的影响；
  2. 将 应用到重子节点上；
  3. 恢复轻子节点的子树对计数数组的影响。

对于一个节点，可能会多次访问，并且容易发现节点被访问的次数等于节点到根节点路径上轻边数量。

又因为任意位置到根节点路径上轻边数量为 ，因此每个节点至多被访问 次，总时间复杂度为 。

set

相比使用数组维护，set 维护的复杂度会多一个 。

直接对树应用 DFS，返回子树的颜色集合（返回时移动构造做到 ）；在父节点合并时，将小的 set 往大的 set 上合并；类似上文的分析技巧，可以证明一个颜色至多被合并 次。又因为合并是 的，因此总的复杂度是 的。

由于不需要考虑撤销对计数数组的影响，这种方法在大多数时候更好实现。

Mo-algo

将树拍成 dfs 序，容易处理出每个子树在 dfs 序上的范围，使用莫队算法数区间颜色数。

由于只有 个询问，因此时间复杂度为 。