CF600E Lomsat gelral

树上启发式合并（dsu on tree）通常用来查询不带修的子树信息，信息要求可合并。

对于一个结点 \(u\)，其步骤如下：

1. 求解其轻儿子的答案，同时清除递归产生的影响。
2. 求解其重儿子的答案，保留递归产生的影响。
3. 将轻儿子子树内的每个结点都合并进答案中，同时成为以 \(u\) 为根的子树产生的影响。

发现每个结点只会在根到该结点路径上的每条轻边处被清空加合并一次，根据重剖的性质这样的轻边最多只有 \(O(\log n)\) 条。所以如果合并一次信息的时间复杂度算 \(O(m)\)，dsu on tree 的时间复杂度就是 \(O(nm\log n)\) 的。

来看这道板子题，合并信息用桶来实现即可。