启发式合并

启发式算法是什么呢？ 启发式算法是基于人类的经验和直观感觉，对一些算法的优化。 说白了,用思维去强行干碎(不是)复杂度

树上启发式合并

原文oi wiki:dsu-on-tree 我们考虑树上的离线问题或者是其他情况可以从树上dp的角度去思考：

例题

例题1例题2

例1关键步骤

1. 写出暴力写法之后，我们可以考虑将最后一颗树的结点保留下来进而省去删除的操作(因为最后一个结点我们可以通过合并的操作来统计最后的x结点的消息)
2. 那么现在的问题就转化成了我们要选择哪一颗树作为最后一颗树呢？很显然是重儿子所在子树。这里有一个需要仔细思考的点，为什么选择重儿子就会影响时间复杂度到log级别呢?想通这个就能理解这题的启发式写法了

代码

启发式需要你拥有钝感力--需要你去不断训练