概述

树上启发式合并,可以简单概括为小的合并到大的上去。

Sack 传送门

要注意的是,删除的时候是直接删除所有信息的,不用考虑其他问题。

启发式合并的要点是,在处理子树的时候,继承重儿子的信息。其他子树的信息都要加上来,然后还原。考虑复杂度。对于一个点,只有在处理的祖先的时候才有可能遍历到。而只有在轻儿子上才会遍历到到祖先有条链,因此有个轻儿子。因此复杂度是的。

CF600E

求子树众数和

如果只考虑一棵树,可以求解。而本题信息是可以合并的,因此每次我们保留重儿子的信息(如果当前这棵树的根是一个重儿子就不清空)。这样每个结点的信息最多贡献次,总复杂度

代码

CF741D

求子树路径上字母任意顺序存在构成回文串的最长路径

由于是回文串,因此我们只关心出现次数的奇偶性。则设表示出现状态为的结点的最大的深度。求经过当前根结点的最长路径,可以枚举子树结点,枚举某一位的出现次数为奇数或者出现次数都为偶数,然后更新当前答案。删除的话直接设为 -INF。显然可以保留重儿子信息。复杂度

代码