启发式合并
定义
在并查集和树上处理离线问题的算法，主要思想是把小集合并到大集合上
做法
树上颜色：一棵树，每个节点都有一个颜色，给定 m 次询问，问以 x 为根的子树有多少种不同的颜色。
轻重剖分，只需要记录重儿子即可。先遍历轻儿子，不计修改。再遍历重儿子，计入修改。最后再遍历轻儿子（dfs序列简化，遍历序列），统计出 root 的答案。再根据递归时要不要计入修改来算。
复杂度
对于重儿子，只会访问一次。对于轻儿子要访问多次。考虑一个点到根的路径上的轻边数量，每多一条轻边，则会被遍历一次，多统计一下。轻边个数最多为 \(O(\log n)\) 条（见重链剖分）。而因为这个点自身答案需要统计故访问次数最多为 \(\log n + 1\)，总复杂度为 \(O(n(\log n+1))=O(n \log n)\)