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 . Merging smaller frequency maps into larger ones drops it to .
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.