1 树上启发式合并

1.1 启发式算法

我并没有找到比较正式的定义，在这里引用 OI Wiki 里的

启发式算法是基于人类的经验和直观感觉，对一些算法的优化。

例子：并查集的按秩合并

1.2 树上启发式合并

基于「减少节点多的子树的处理次数」的思想为主的算法

1.3 实现

我们希望节点多的子树处理次数尽可能少，也就是我们希望重儿子的处理次数尽可能少

注意到许多树上问题的处理过程是可延续的，即当前子树的处理完后可以直接将数据移交到父亲节点继续处理

基于这点，我们可以优先处理重儿子，然后直接继承到父亲节点。这样对于一个节点来说，其重儿子只需要处理一次，其轻儿子需要处理两次。

因为从树上任意一条路径上，关键点（即轻儿子）在 $O(\log(n))$ 范围内，所以这东西的复杂度是 $O(n\log(n))$ 的。

Continue reading “树上启发式合并(dsu on tree)简介”