树上启发式合并小结
概述
树上启发式合并,可以简单概括为小的合并到大的上去。
要注意的是,删除的时候是直接删除所有信息的,不用考虑其他问题。
启发式合并的要点是,在处理子树的时候,继承重儿子的信息。其他子树的信息都要加上来,然后还原。考虑复杂度。对于一个点,只有在处理的祖先的时候才有可能遍历到。而只有在轻儿子上才会遍历到。到祖先有条链,因此有个轻儿子。因此复杂度是的。
CF600E
求子树众数和
如果只考虑一棵树,可以求解。而本题信息是可以合并的,因此每次我们保留重儿子的信息(如果当前这棵树的根是一个重儿子就不清空)。这样每个结点的信息最多贡献次,总复杂度。
CF741D
求子树路径上字母任意顺序存在构成回文串的最长路径
由于是回文串,因此我们只关心出现次数的奇偶性。则设表示出现状态为的结点的最大的深度。求经过当前根结点的最长路径,可以枚举子树结点,枚举某一位的出现次数为奇数或者出现次数都为偶数,然后更新当前答案。删除的话直接设为 -INF。显然可以保留重儿子信息。复杂度。
修订记录
- 2019年10月7日 创建文章