树上启发式合并,Dsu on tree.

一类可以解决无修改的子树特征查询的算法(基于树链剖分的轻重链思想)

看下面这样一个问题:

给定一棵树,求每个节点子树内颜色最多的所有节点的颜色和。

这个问题可以用Dsu很好的解决。

首先对该数进行轻重链剖分(一个DFS),然后进行第二个DFS。

[DFS实现]

首先先求出每个轻儿子的答案,然后在你记录颜色数量的数组上消除他们的影响。

然后解决重儿子,不清空影响,再将轻儿子的影响添加进去,记录答案。

[复杂度]

可以这么考虑:只有DFS到了轻儿子时,才会将轻儿子的贡献合并到上一级重儿子上。

树链剖分将树分割为不超过条重链,每个节点最多向上合并次。

所以整体复杂度O()。

 

Educational Codeforces Round 2 E