树上启发式合并小结

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