Dsu on Tree （树上启发式合并）不是很详的解
引子
先来个例题耍耍。
给出一棵 $n$ 个节点以 $1$ 为根的树，节点 $u$ 的颜色为 $c_{u}$，现在对于每个结点 $u$ 询问以 $u$ 为根子树里一共出现了多少种不同的颜色。
$n \le 2 \times 10^{5}$。
（没错就是 OIWiki 上的例题。。。）
流程
先把算法流程打出来方便讲。
我们设一个数组 $cnt[]$ 用来记录颜色每个种类的数量。
- 先树链剖分找出每个节点的重儿子；
- 对于每个节点 $u$ 优先遍历其轻儿子，并计算出轻儿子的答案，但不保留遍历轻儿子对 $cnt[]$ 数组的影响；
- 接着遍历 $u$ 的重儿子，保留遍历重儿子对 $cnt[]$ 数组的影响；
- 再遍历一遍 $u$ 的轻儿子，保留再次遍历轻儿子对 $cnt[]$ 数组的影响，得到 $u$ 的答案。
分析
该算法的重点就是先后两次遍历轻儿子。
那么为什么不将两次遍历合并呢？
考虑如果两次合并，那么轻儿子对 $cnt[]$ 数组的影响就会使重儿子遍历前后的数据难以储存，而如果两次分开操作则遍历重儿子时数组是空的，方便遍历时储存。
那么为什么不先遍历重儿子呢？显然这样是不划算的（所以才叫启发式合并啊）。
那合并后先遍历重儿子呢？ 显然这也是不划算的，因为轻儿子还没有遍历和处理过，带着重儿子的一堆数据显然是跑不快的。
码
懒得打。