Distinct Colors - Lessons

You saw how small-to-large merging avoids recopying large sets repeatedly. By identifying the largest child and reusing its set, you minimize element moves. By always merging into the largest child's set, you guarantee $O(\log n)$ moves per element across the entire tree.

This pattern works anytime you need to combine child results into a parent's result using sets, maps, or similar structures. The key is choosing the right merge direction.