• 树上启发式合并小结

    • 算法适用：dsu on tree主要是解决不修改的子树问题
    • 首先看题
    • 先想一下暴力算法，对于每一次询问都遍历整棵子树，然后统计答案，最后再清空cnt数组
    • 删除信息过程耗了太多的时间，最坏情况是时间复杂度为 O(n2)
    • 现在考虑优化算法
    • 先说以下大概过程
    • 大概过程
    • 1.处理轻子树及其子树的答案，删除贡献
    • 2.处理重子树及其子树的贡献，并不删除贡献
    • 3.暴力统计所有轻子树及其子树的贡献与上一步统计的贡献合并，得到节点u的答案
    • 4.删除轻子树及其子树的贡献
    • 回顾暴力做法我们可以发现在统计节点u的儿子节点的时候，最后一个儿子节点对cnt数组的贡献可以不用清除，换句话说就是统计u节点的答案时，最后一个遍历的儿子节点可以不需要在统计u节点的答案时再次去遍历了，这并不会影响答案，原因是我们的做法计算完u的最后一个儿子节点的答案后我们要计算u节点的答案，恰好最后一个节点的信息就包括在u当中，因此可以不用清空cnt数组
    • 简洁来讲就是
    • 我们每次进入一棵子树计算答案时，都要把计算上一棵子树的数据清除
    • 为什么，如果我们带着上次计算后的结果去计算新子树，答案肯定是不对的
    • 但是，我们最后一棵子树不需要清除，因为我们不用再进入新子树了
    • 既然可以少遍历一颗子树，那自然是让这颗子树越大越好（这样我们就可以少遍历点，进而减少时间复杂度），这不恰好就是我们的重儿子嘛，它就是众多子树中最大的那一棵
    • 所以我们先把每个点的重儿子求出来，在遍历子树求答案时，把重儿子这个点最后遍历，这样我们就可以尽量少的遍历点，会使得时间最优，这就是树上启发式合并的关键思想，也是过程的由来
    • 根据上面的分析，显然要选一棵最大的子树最后跑，会使得时间最优，这就是树上启发式合并的关键思想，也是过程的由来
  • 相关阅读:
    4、MySQL 多版本并发控制原理-数据可见性算法
    力扣105. 从前序与中序遍历序列构造二叉树
    java企业员工健康体检预约系统 python/php小程序 医院体检预约系统
    任务清单小功能的实现（任务的增、删、改、查、存储）使用Vue实现
    python-28-日志模块Loguru的应用
    @Valid和 @Validated
    11-注意力机制
    typescript ts 基础知识之接口、泛型
    Java 超经典面试题
    除了账号防关联外，亚马逊卖家还要注意什么？
  • 原文地址：https://blog.csdn.net/weixin_59624686/article/details/126056035