Lessons - Lomsat gelral

Lesson: when you need to merge data from multiple subtrees, and naive merging (recompute from scratch) is too slow, use Small-to-Large merging.

This problem needs frequency counts for every subtree. Recomputing from scratch is $O(n^2)$. Merging smaller frequency maps into larger ones drops it to $O(n \log n)$.

Anytime you see "compute something for every subtree by combining children's results," think Small-to-Large. It is the standard optimization for subtree aggregation problems.