DSU on Tree: 名字的由来
在算法竞赛（CP）中，DSU on Tree 是一个处理树上静态路径或子树查询的高效技巧。然而，初学者常会产生一个巨大的困惑：
“为什么这个算法叫 DSU（并查集）on Tree，代码里却连一个 find() 或 parent[] 都没有？”
1. 核心思想的传承：启发式合并
这个名字的本质不在于“数据结构”，而在于“算法思想”。
- 在标准的 DSU (Disjoint Set Union) 中，为了保证效率，我们会使用 按秩合并（Union by Rank/Size）。即：将小的集合合并到大的集合中。
- 这种“由小推大”的策略被称为 启发式合并 (Heuristic Merging)。它可以保证 $n$ 个元素在合并过程中的总时间复杂度为 $O(n \log n)$。
2. 树上的“重”与“轻”
DSU on Tree 实际上是 树上启发式合并（Static Top-Tree 或 Sack 算法）。它的操作逻辑如下：
- 递归处理所有 轻儿子 (Light Son)，并在处理完后清空计数桶（释放内存/状态）。
- 递归处理 重儿子 (Heavy Son)，处理完后保留其状态。
- 将轻儿子的信息暴力暴力重新加入到重儿子的状态中，从而得到当前节点的状态。
这个过程本质上是：将轻儿子（较小的子集）的信息，合并到重儿子（较大的子集）的状态中。
3. 为什么不叫 Heuristic on Tree？
虽然“树上启发式合并”在中文语境下很流行，但在国际竞赛圈，人们习惯称其为 DSU on Tree，原因有二：
- 复杂度关联： 两者都利用了“小并大”来将暴力复杂度从 $O(n^2)$ 压低到 $O(n \log n)$，证明逻辑完全一致。
- 代码简洁性： 在一些早期的题目中，这类问题确实可以通过真正的 DSU（配合撤销操作）在树上移动来解决。虽然现代写法（利用重链剖分）效率更高，但
DSU on Tree 这个简短的名字被沿用了下来。
4. 结论
"DSU on Tree 是没有 DSU 的 DSU，正如老婆饼里没有老婆。"
它代表的是一种权衡：通过识别“重”的部分（Heavy）并尽可能复用它的状态，来避免昂贵的重复计算。这种“贪心”地保留最大子状态的思想，正是 DSU 算法的灵魂所在。