树上启发式合并(DSU on Tree)

树上启发式合并(DSU on Tree)是一种用于高效解决静态树上子树统计问题的离线算法技巧,其名称源于并查集中的启发式合并思想,但实现上通常并不真正使用并查集结构。它适用于对每个节点询问其子树内某种统计量的场景。

概述

许多问题需要对树上每个节点回答关于它子树的询问,例如子树内出现次数最多的颜色、不同颜色的数目等。朴素做法是对每个节点重新遍历其子树,复杂度可达平方级。树上启发式合并通过巧妙地保留重儿子的统计信息,把总复杂度降到对数级别,是竞赛与工程中处理此类问题的经典手段。

核心原理

算法基于树链剖分中的重儿子概念,即子树规模最大的儿子。处理某节点时的步骤如下:

• 先递归处理所有轻儿子,并在处理完后清除它们对全局统计数组的影响。
• 再递归处理重儿子,并保留其统计信息不清除。
• 把当前节点及其所有轻儿子子树的贡献重新加入统计数组,此时数组恰好包含整棵子树的信息,回答该节点的询问。
• 若当前节点是父节点的轻儿子,则处理完后清空贡献;若是重儿子则保留。

每个节点被作为轻儿子重新计算的次数不超过它到根路径上轻边的条数,由重链剖分性质该数量为对数级,故总复杂度为 O(n log n)。

应用场景

该技巧广泛用于算法竞赛中的子树统计类题目,如统计每个子树内颜色种类、众数、满足某条件的点对数量等。它也可推广到需要维护可加可撤销信息的场景,是离线树上问题的重要工具。

常见问题

问:它和线段树合并有什么区别?答:线段树合并为每个节点维护一棵动态开点线段树并真正合并,空间较大但支持在线查询;树上启发式合并只用一个全局数组反复增删,空间小、常数小,但要求信息可撤销且通常离线。

问:为什么复杂度是 O(n log n) 而不是平方?答:关键在于重儿子的信息被保留,只有轻儿子子树被反复清算,而任意节点到根的轻边数量为对数级,累加后即得对数复杂度。