DSU on Tree

一句话理解

DSU on Tree 树上启发式合并。

为什么要学

子树询问离线。

讲解

轻儿子算完扔掉，重儿子保留。O(n log n)。

例子

sack。

常见错误

• 询问在线且改全局。
• 没先算轻再留重。