树上启发式合并（dsu on tree）

__ryp__ · 2024-05-14 19:54:59 · 个人记录

暴力子树加最差复杂度是方的，因为每个点会被加入许多次。准确的说，会暴力加其深度加一次，因为其到根的链上每个点的答案都由它贡献。

发现 DFS 整体是有一条回溯链的。这条链上的点是不需要重复加入与删除的。取这条链为重链，那么有对任意点，其到根的轻边是 \log 级的，整体复杂度是 O(n\log n) 的。