DSU on Tree 不是并查集，而是基于重链剖分的离线子树统计优化算法；它通过先处理轻儿子（递归后清空）、再处理重儿子（递归后保留）来实现 $O(n \log n)$ 复杂度，核心是复用重儿子统计结果而非真正合并集合。
DSU on Tree 不是并查集，别被名字骗了；它本质是暴力优化，核心在于“先算轻儿子、再清空，最后算重儿子、保留结果”。
为什么叫 DSU on Tree 却不用 union 或 find？
名字是历史遗留——它类比了并查集“合并集合”的行为，但实际没调用任何并查集操作。真正做的是：对每个节点，把所有子树信息“合并”进当前节点的统计容器（比如 std::map 或数组），而利用子树大小关系跳过部分清空开销。
常见误解是去翻 std::disjoint_set 文档，结果一无所获。记住：你只用写 DFS + 手动转移计数，不涉及任何 union_by_size 或路径压缩。
- 重儿子（heavy child）必须提前通过一次 DFS 预处理出来，用
sz[u]和hson[u]数组存 - 轻儿子子树每次都要完整遍历并清空，不能复用；重儿子子树的结果直接继承
- 如果你漏了“先递归轻儿子再清空”，而是反过来，会多出 O(n log n) 次无效插入，性能崩盘
dfs1 和 dfs2 分两遍的必要性
第一遍 dfs1 只干一件事：算子树大小、定重儿子。不能省，也不能和第二遍混在一起——因为 dfs2 里要靠 hson[u] 决定是否跳过清空，而这个值必须在进入 dfs2(u) 前就确定。
立即学习“C++免费学习笔记（深入）”；
第二遍 dfs2 才执行真正的 DSU 流程：轻儿子递归 → 清空 → 重儿子递归（不清空）→ 再把自己加进去 → 处理当前节点的查询。
-
dfs1中的sz[u] = 1必须放在循环外初始化，否则轻儿子会干扰重儿子判断 -
dfs2的参数通常带一个keep标志，表示“算完要不要清空当前子树数据”；根节点调用时传false，重儿子递归传true - 如果把
keep逻辑写反（比如重儿子也清空），复杂度退化成 O(n²)
怎么选统计容器？std::map 还是数组？
取决于值域。如果颜色/类型编号在 [1, n] 范围内，直接用 cnt[i] 数组最快；如果值域大或稀疏（比如点权是 long long），就得用 std::unordered_map 或 std::map，但要注意后者单次插入是 O(log n)，整体仍是 O(n log² n)。
更关键的是：清空操作成本。数组清空不能 memset 全局，只能按实际修改过的下标逐个置 0；std::map 就直接 clear()，但频繁 clear 仍比数组慢。
- 若问题只问“子树中出现次数最多的颜色”，可以只维护
max_cnt和ans_cnt两个变量，避免存全量cnt - 不要在
dfs2里声明局部std::map然后反复 copy，那会触发大量构造/析构，卡常严重 - 全局容器 + 手动回滚（记录修改位置）比每次新建更快，尤其在重儿子复用场景下
调试时最常见的三个错误现象
跑小样例没问题，一交就 WA 或 TLE？大概率栽在这三处：
- 重儿子判断写成
if (sz[v] > sz[u])（v 是邻居，u 是父），应为if (sz[v] > sz[hson[u]])，否则重儿子永远是 0 - 清空轻儿子子树时，遍历的是整棵树节点而非该子树实际修改过的点，导致清空范围过大甚至越界
- 处理当前节点前忘了把它自己加进统计（比如
cnt[color[u]]++），导致所有查询少算根节点
最隐蔽的坑是：重儿子递归后，你以为数据还在，但如果你在重儿子内部又调了 clear() 或用了局部容器，那继承就失效了——DSU on Tree 的“保留”完全依赖你手动控制容器生命周期。
