DSU On Tree / Small-To-Large Ladder

This lane is for rooted-tree subtree queries where each child contributes a mergeable container and the merge itself is the real complexity bottleneck.

Who This Is For

Use this ladder if:

• plain Tree DP feels too small-state for the subtree statistic
• Euler Tour / Subtree Queries does not close the problem with one interval structure
• you keep seeing map or set merges inside DFS and want the exact contest-safe route

Core

• rooted tree
• one subtree container per node
• merge small child container into large surviving container

Target skill:

• know why the amortized bound comes from doubling container size after every move

Exact Starter

• small-to-large-subtree-merge.cpp

Target skill:

• compute one subtree statistic for every node by bottom-up container merges

Flagship Rep

• Distinct Colors

Target skill:

• turn subtree distinct-count queries into color -> frequency map merges

Stretch

• Lomsat gelral
• compare with Tree DP
• compare with Mo's Algorithm

Target skill:

• know when the statistic is still a mergeable subtree container and when you should switch to a different tree-query family

Exit Criteria

You are ready to move on when:

• you can explain the doubling argument without code
• you know why swap is part of the algorithm, not micro-optimization
• you can tell when this route is lighter than Euler flattening plus another structure

External Practice

• CSES - Distinct Colors
• Codeforces - Lomsat gelral
• USACO Guide - Small-To-Large Merging

Tutorial Link

• DSU On Tree / Small-To-Large