Small-to-Large Merging
Amortize repeated subtree merges by always moving the smaller container into the larger one.
Small-to-Large Merging
The main note is rendered from the TeX source. Code lives in a separate C++ file so the write-up stays readable.
Overview
Small-to-large merging is the trick I reach for when each subtree carries a container and naive merging would be quadratic. The rule is simple: always merge the smaller container into the larger one.
When to Use It
Use it when:
you are doing DFS on a tree,
each subtree needs a set, map, frequency table, or similar container,
parent states are formed by merging all child containers.
Core Idea
After solving every child subtree, keep the largest child container as the base and insert all elements from smaller child containers into it. That strategy limits how many times one element can move.
Key Insight
Whenever one element moves, it moves into a container at least twice as large as before. So one element can be moved at most \(O(\log n)\) times overall. That is the amortized reason the technique is fast.
Operations / Main Technique
DFS the children first,
select the largest child container as the main container,
merge smaller child containers into it,
answer the current node's query from the merged state.
Worked example.
If each subtree stores the set of colors appearing in it, then small-to-large merging gives all subtree color counts in roughly \(O(n \log n)\) instead of repeatedly rebuilding sets from scratch.
Correctness Intuition
The merge order does not affect the final container contents, only the cost. Since all child data eventually lands in the parent's chosen base container, the subtree summary remains correct.
Complexity Analysis
With balanced-tree maps or sets, many common uses run in \(O(n \log^2 n)\) or \(O(n \log n)\), depending on the exact container operations.
Implementation
The code shows the classic subtree-color-count example using maps. The same pattern applies to sets, multisets, and other associative containers.
Common Pitfalls
Forgetting to swap so the larger container stays as the base.
Copying containers instead of reusing pointers or references.
Using the trick when the merge operation itself is too expensive or not associative enough.
Variants / Extensions
DSU on tree, which is related but organized differently.
Maintaining best frequency or color answer alongside the map.
Using vectors plus coordinate compression when keys are small.
Practice Problems
Number of distinct colors in every subtree.
Frequency-based subtree queries.
Merge subtree statistics where order is irrelevant.
References
Code
Contest-ready reference implementation for the idea explained above.
struct SmallToLargeDistinctColors {
vector<vector<int>> tree;
vector<int> color;
vector<int> answer;
vector<map<int, int>> bag;
explicit SmallToLargeDistinctColors(int n)
: tree(n), color(n), answer(n, 0), bag(n) {}
void add_edge(int u, int v) {
tree[u].push_back(v);
tree[v].push_back(u);
}
void dfs(int v, int parent = -1) {
bag[v][color[v]] = 1;
for (int to : tree[v]) {
if (to == parent) continue;
dfs(to, v);
if (bag[to].size() > bag[v].size()) {
swap(bag[to], bag[v]);
}
for (auto [key, freq] : bag[to]) {
bag[v][key] += freq;
}
}
answer[v] = (int)bag[v].size();
}
};
Source Files and Assets
Raw files are still available here when you want the original TeX, C++, or statement assets.