DSU on tree 树上启发式合并

· · 算法·理论

DSU on Tree 树上启发式合并

树上启发式合并是一种非常常用来处理有关于子树内一些有关于 “次数”，“路径异或”之类的问题，虽然算法本身比较困难，但是学会理解了模板就非常简单了。

树上启发式合并，专门用来处理有关于次数的问题，需要维护的信息很多，例如 son_x（代表节点 x 的重子节点）等。

说到处理次数的问题，而且是在一棵树上，可以发现这非常困难，于是首先想到的就是暴力求解，对于每一棵子树中，每次进行枚举进行统计答案，这样子每次计算一边的时间复杂度就是 O(n^2)，很明显在很多题无法通过，于是树上启发式合并（DSU on Tree）就可以很好的解决这个问题。

我们来分析暴力的过程，先对一个父节点 x 的一个儿子节点进行遍历子树的过程，然后清空这次遍历使用的桶数组，然后在遍历下一棵子树，我们发现，每次都进行清空操作其实完全没有必要，因为最后一个子树完全不需要被清空，因为后面没有需要别遍历的子树，那么如果我们想要使得时间复杂度达到最优，那么就需要使得这颗子树的大小达到最大（也即 x 的重儿子）。

所以每次我们进行 DSU 操作时，不去清空这个重儿子，就会使得时间复杂度提升，看上去好像没有优化，但是经过仔细证明后可以得出，其实时间复杂度是 O(n \log n) 的，符合我们的需求。

例题：

题目意思非常简单，给定每一个节点的颜色，要求求出对于每一个节点的子树，其中出现次数最多颜色的编号之和。

看到出现的次数且是在一棵树上，很容易想到使用 DSU 求解，所以用这道题来演示 DSU 模板的写法：

https://codeforces.com/contest/600/submission/332590072

题目意思基本上和上题一样，其实处理的思路也是差不多一样的，不过两题的不同点在于一个题目求得是出现最多次数的颜色编号之和，另一个则是求出出现次数 \ge k 的子节点个数。

同样使用 cnt_x 维护 x 颜色的出现次数，不过需要多使用一个 num_x 数组来维护出现次数 \ge k 的元素个数，在 clear_ans 数组变换答案时进行处理即可。

注意本题有多次询问，所以无法直接处理，不妨把每一个询问离线，然后挂到每一个节点上去询问，接着处理答案直接最后输出即可。

https://codeforces.com/contest/375/submission/332591162

这题不一样，不过还是一个 DSU 的板子题，给定每一个节点的父亲节点和其名字，要求 m 次询问操作，每次询问你一个节点 x 的 k 级儿子有多少个不同的名字。

看上去很难做，其实仔细想想，还是有关于统计次数的问题，只是多了一个字符串的限制，和 k 级儿子，不妨在 dfs1 时预处理重儿子时求出所有点的深度，然后用 set 在每一个深度处记录每一个名字的出现与不出现，在最后清理时，将整个 set 清空即可。

https://codeforces.com/contest/246/submission/332593867

这是一道很有训练价值的 DSU 题，稍微比前一题略难，不应该是蓝。

定义 k 级表亲为存在一个人 z，既是 x 也是 y 的 k 级祖先，称 x 和 y 互为 k 级表情，每次询问问一个点的 k 级表亲有多少个。

看到了次数想到了树上启发式合并，但是由于是 k 级表亲，无法向上维护，所以不妨我们想想，求出 k 级表亲的树上，不就是求出其 k 级祖先的 k 级儿子有多少个吗？所以使用倍增算法进行预处理操作，先算出 x 的 k 级祖先是谁，然后使用 DSU 求出其 k 级儿子的个数即可。

https://codeforces.com/contest/208/submission/332598595

首先分析题目，每次询问 x 和 y 要求你求出 x 子树内所有深度为 y 的子节点的字母在经过重排后能否组成回文串。

考虑回文串的性质，很容易知道重排后能组成回文串的必要条件是所有字母的出现次数为奇数的个数需要不超过 1 个，所以使用 DSU 统计出现次数然后在每一次离线暴力常数 26 判断即可。

https://codeforces.com/contest/570/submission/332603145

此题为上一题扩展，CF 2900 不止紫。

思路主要的想法来自与 CF570D，重排后能组成回文串的必要条件是所有字母的出现次数为奇数的个数需要不超过 1 个，所以可以考虑到奇数偶数的情况可以直接进行一个 2^{22} 的 22 位状态压缩进行转移，每一次枚举是哪一个字母的出现次数为奇数，需要考虑非常多情况，而且码量巨大很容易写错，且需要注意表示状态压缩数组的 D 数组的大小需要开到 2^{22}（应该只有我这个唐龙才会犯这种错误而导致调了 20min）。

https://codeforces.com/contest/741/submission/332611183