今天模拟赛 T2 用到了，所以来浅浅地学一下 DSU on tree。
对于一类树上问题（大多是和路径有关的），其暴力复杂度通常会带上一个 \(n^{2}\)，这时利用启发式合并就可以将其优化到 \(n \log n\)。
具体地，假设搜索到了 \(u\) 结点，令 \(son_{u}\) 表示结点 \(u\) 的重儿子，那么：
- 先对 \(u\) 的所有非重儿子 \(v(v \not= son_{u})\) 搜索，搜索结束后消除这次搜索带来的影响，或者说回溯，包括但不限于清空桶，撤回标记等等。
- 搜索 \(son_{u}\)，并且保留这次搜索带来的影响，即不回溯。
- 再次对 \(u\) 的所有非重儿子 \(v(v \not= son_{u})\) 搜索。
第一步可以和第二步可以统计出 \(u\) 的每个子树的答案，第三步是为了求出 \(u\) 的信息并统计答案。
因为 \(u\) 的各个信息可以由其子树继承/合并而来，所以我们可以选择一个子树，在其搜索结束后不回溯，直接继承/合并到当前节点来，按照人类智慧来看，我们保留子树大小最大的子树的信息是最划算的，这就是树上启发式合并的精髓。
复杂度证明不会，OI wiki 上的证明看不懂，有没有好心人给我讲讲/kk
标签：子树,DSU,tree,son,搜索,回溯 From： https://www.cnblogs.com/A-box-of-yogurt/p/18139133