树上启发式合并是某些神仙题目的常见操作。
这里有一个讲得详细一点的，不过为了深刻记忆，我还是再给自己讲一遍吧！
DSU（Disjoint Set Union），别看英文名挺高级，其实它就是并查集……
DSU on tree，也就是树上的启发式合并（众所周知，并查集最重要的优化就是启发式合并）。
然后咱们来考虑一个基础题：给出一棵树，每个节点有颜色，询问一些子树中不同的颜色数量（颜色可重复）。祖传数据（$100000$）。
当然，这道题可以被各种方法切，比如带修莫队（做法自行百度）。
但莫队的时空复杂度是 $O(n\times sqrt(n))$ 的，稍微差点。
又比如这里讲的主席树。
但主席树的空间复杂度是 $O(n\times log^2(n))$（虽然时间复杂度还是 $O(n\times log(n))$），我们考虑换一个严格 $O(n\times log(n))$ 的做法。
没错，就是树上启发式合并。
原文：https://www.cnblogs.com/scx2015noip-as-php/p/10006873.html