树上启发式合并(DSU on tree),可以概括为小的合并到大的上去(small to large1)。

具体地说,设表示我们要求的结点信息,而代表结点本身的数据依赖于子树内结点的数据,但这种数据并不能简单合并,需要挨个遍历以更新信息。不过这种数据具备可减性。

这时我们就可以考虑利用启发式合并来离线地计算每个结点

考虑 DFS,我们先计算子结点的信息,在计算完后我们根据这个结点的身份决定是否让其父亲继承它的信息以及其子树的数据。如果继承,那么就保留其数据,否则就删除。

而身份判断的标准就是该结点是重儿子。所谓的重儿子指子树大小最大的儿子。

考虑将树重链剖分,那么可以发现结点的数据会被遍历当且仅当我们正在计算的信息,且

  • 的祖先
  • 的轻儿子的子树里

这等价于:到根链上的重链的底端。

因此这样的的个数是的。于是启发式合并的复杂度是的。

CF600E

求子树众数和

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

代码

CF741D

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

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

代码

1. https://codeforces.com/blog/entry/44351