树上启发式合并小结

算法适用：dsu on tree主要是解决不修改的子树问题
首先看题
先想一下暴力算法，对于每一次询问都遍历整棵子树，然后统计答案，最后再清空cnt数组
删除信息过程耗了太多的时间，最坏情况是时间复杂度为 O(n2)
现在考虑优化算法
先说以下大概过程
大概过程
1.处理轻子树及其子树的答案，删除贡献
2.处理重子树及其子树的贡献，并不删除贡献
3.暴力统计所有轻子树及其子树的贡献与上一步统计的贡献合并，得到节点u的答案
4.删除轻子树及其子树的贡献
回顾暴力做法我们可以发现在统计节点u的儿子节点的时候，最后一个儿子节点对cnt数组的贡献可以不用清除，换句话说就是统计u节点的答案时，最后一个遍历的儿子节点可以不需要在统计u节点的答案时再次去遍历了，这并不会影响答案，原因是我们的做法计算完u的最后一个儿子节点的答案后我们要计算u节点的答案，恰好最后一个节点的信息就包括在u当中，因此可以不用清空cnt数组
简洁来讲就是
我们每次进入一棵子树计算答案时，都要把计算上一棵子树的数据清除
为什么，如果我们带着上次计算后的结果去计算新子树，答案肯定是不对的
但是，我们最后一棵子树不需要清除，因为我们不用再进入新子树了
既然可以少遍历一颗子树，那自然是让这颗子树越大越好（这样我们就可以少遍历点，进而减少时间复杂度），这不恰好就是我们的重儿子嘛，它就是众多子树中最大的那一棵
所以我们先把每个点的重儿子求出来，在遍历子树求答案时，把重儿子这个点最后遍历，这样我们就可以尽量少的遍历点，会使得时间最优，这就是树上启发式合并的关键思想，也是过程的由来
根据上面的分析，显然要选一棵最大的子树最后跑，会使得时间最优，这就是树上启发式合并的关键思想，也是过程的由来

相关阅读:
springcloud gateway转发后getServerName被更改的问题
c数组与结构体
项目引入jar从私服Nexus 拉去遇到的一个问题
3 开源鸿蒙OpenHarmony4.1源码下载、编译，生成OHOS_Image可执行文件的最简易流程
【SQL刷题】DAY15----SQL联结表专项练习
mybatis查询PostgreSQL报错：无法确定参数 $1 的数据类型
JVM内存模型（JMM）
YOLO系列之yolov1解读（1）
多肽RGD修饰乳清白蛋白/肌白蛋白/豆清白蛋白/蓖麻蛋白/豌豆白蛋白1b ( PA1b)纳米粒（实验原理）
03 矩阵与线性变换

原文地址：https://blog.csdn.net/weixin_59624686/article/details/126056035