Subtree aggregate queries
Suppose each node has a color and you must answer, for every node, a question about the colors in its whole subtree, such as how many distinct colors appear. Recomputing each subtree from scratch repeats too much work.
Keep the heavy child
The small to large technique, often called DSU on tree, processes a node by reusing the data of its heavy child, the child with the largest subtree.
- Recurse into the light children first and clear their data.
- Recurse into the heavy child last and keep its accumulated data.
- Then add the light children's nodes back into that kept structure.
Because each node is added only when it lies in a light subtree, and a node can be in a light subtree on only a few levels up the tree, the total added work is small across the whole run.
Why it is efficient
Every node is inserted a limited number of times, bounded by the number of light edges above it, which grows only with the logarithm of the size. So the heavy reuse keeps total cost close to the cost of a single tree traversal with a light overhead factor.
Key idea
Keep the heavy child's accumulated data and only re add light subtree nodes, so each node is inserted just a few times overall.