树上启发式合并

文章内容选自OI Wiki
参考博客

内容：

树上启发式合并（dsu on tree）对于某些树上离线问题可以速度大于等于大部分算法且更易于理解和实现的算法。
他是用来解决一类树上询问问题，一般这种问题有两个特征：

只有对子树的询问

没有修改

一般就可以签上dsu on tree

例题：
给出一棵 n个节点以 1为根的树，节点 u的颜色为cu ，现在对于每个结点 u询问 u子树里一共出现了多少种不同的颜色。
n<=2e5

树套树可以解决，如果可以离线的话，树上莫队复杂度带根号，现在我们要用一个带log的算法。
对于直接暴力复杂度为O(n^2),即对每一个子节点进行一次遍历，
对于每个节点的答案是由其子树和其本身得到的，现在考虑利用这个性质处理问题
我们预处理出每个节点子树的大小和其重儿子，重儿子同树链剖分一样，都是拥有节点最多子树的儿子，这个过程O(n)求
用cnt[i]表示颜色i出现的次数，ans[u]表示节点u的答案
对于一个节点u，我们按以下步骤遍历：
3. 先遍历u的轻(非重)儿子，并计算答案，但不保留遍历后对cnt数组的影响(消除递归产生的影响)
4. 遍历重儿子，保留对cnt的影响(不消除递归的影响)
5. 再遍历u的轻儿子的子树节点，加入这些结点的贡献，得到u的答案

对于一个节点，我们遍历一次重儿子，两次非重儿子，最划算
为什么不合并第一步和第三步呢，因为cnt数组不能重复使用，不然空间复杂度太高，需要O(n)内完成
若一个节点u被遍历了x次，则其重儿子被遍历x次，轻儿子被遍历2x次
这样的复杂度是O(nlog n)

int sz[N],son[N];void dfs1(int x){/* 求解重儿子 */sz[x] = 1;for(int i = head[x]; i; i = e[i].next){int y = e[i].to;dfs1(y); sz[x] += sz[y];if(sz[y] > sz[son[x]]) son[x] = y;} }void Delete(int x){/* 删除的内容 */for(int i = head[x]; i; i = e[i].next) Delete(e[i].to); }void modify(int x,int fa){/* 更新的内容 */for(int i = head[x]; i; i = e[i].next) modify(e[i].to,fa); }void ins(int x){/* 插入的内容 */for(int i = head[x]; i; i = e[i].next) ins(e[i].to); }void dfs2(int x){/* 求解轻儿子并清空 */for(int i = head[x]; i; i = e[i].next)if(e[i].to != son[x]) dfs2(e[i].to), Delete(e[i].to);/* 求解重儿子并保留 */if(son[x]) dfs2(son[x]);/* 用重儿子更新答案 *//* 枚举轻儿子更新答案，并加入轻儿子 */for(int i = head[x]; i; i = e[i].next) if(e[i].to != son[x]) modify(e[i].to,x), ins(e[i].to);/* 用所有儿子更新答案 */ }

证明：

性质：一个节点到根的路径上轻边个数不会超过logn条
我们考虑一个点会被访问几次？
一个点被访问只有两种情况：

在暴力统计轻边的时候访问到，次数<logn

通过重边/在遍历的时候被访问到，只有一次

如果统计一个点的贡献的复杂度为O(1)的话，该算法的复杂度为O(nlogn)

应用

可以水一些树套树的题，也可以把树上莫队O(n√m)吊打
例题：
CF741D Arpa’s letter-marked tree and Mehrdad’s Dokhtar-kosh paths
CF600E Lomsat gelral
CF570D Tree Requests
CF208E Blood Cousins
CF246E Blood Cousins Return
CF1009F Dominant Indices
CF375D Tree and Queries

总结

以上是生活随笔为你收集整理的树上启发式合并的全部内容，希望文章能够帮你解决所遇到的问题。

如果觉得生活随笔网站内容还不错，欢迎将生活随笔推荐给好友。