Small-to-Large
DSU on Tree (Sack)
· ☕ 9 min read · ✍️ k4i
DSU on tree answers subtree queries by keeping the largest child's contribution and rebuilding only the small parts. The trick is not union-find; it is small-to-large merging hidden inside a DFS.
DSU on Tree (Sack)