dsu on tree

搬运自 https://codeforces.ml/blog/entry/44351 dsu on tree，中文名树的启发式合并，是利用了重链剖分后一个结点到根的轻链数目是 $\log n$ 级别的性质的一种优化了的暴力算法，时间复杂度一般为 $O(n \log n)$ dsu on tree 一般解决的是不带修改对子树内的询问，可以通过对所有儿子暴力求答案，但删除轻儿子的结果，保留重儿子的结果，从而保证了复杂度。