Chapter 11 · Advanced Tree Algorithms
Small-to-Large Merging
Why merging the smaller container into the larger one gives O(n log n) total work, and the dozen problems where that one line is the whole solution.
When combining the data of several children into their parent, always iterate over the smaller structure and insert into the largest one (then rename/merge pointers), never the reverse.
In a DFS that merges children's sets into the parent's, each vertex (element) is re-inserted at most log2 n times, so the total number of insertions is O(n log n), and O(n log2 n) with std::set/map (log per insertion) or O(nlog n) with unordered_map.
When an element is moved, it goes from a container of size a into one of size b ≥ a, so the container holding it at least doubles. Its size can double at most log2 n times before reaching n. Multiply by the cost of one insertion. ∎
// "for every vertex v: how many distinct colours appear in v's subtree?"
vector<unordered_map<int,int>*> cnt(n); // colour -> occurrences
vector<int> ans(n);
int dfs(int v, int p) {
auto best = new unordered_map<int,int>(); int bestsz = 0, idbest = -1;
for (int to : g[v]) if (to != p) {
int sz = dfs(to, v);
if (sz > bestsz) { bestsz = sz; idbest = to; }
}
if (idbest != -1) { delete best; best = cnt[idbest]; } // steal the big one
(*best)[colour[v]]++;
for (int to : g[v]) if (to != p && to != idbest) {
for (auto &[c, k] : *cnt[to]) (*best)[c] += k; // small into large
delete cnt[to]; cnt[to] = nullptr;
}
cnt[v] = best; ans[v] = best->size();
return best->size();
}What the trick solves
- distinct colours / values per subtree (the above),
- "the most frequent colour in each subtree" (CF 600E Lomsat gelral, the canonical statement),
- subtree set intersection queries: "does subtree u contain a vertex of colour c?" → answer with maps built once, O(1) per query after O(nlog n),
- merging tries: each node's subtree trie built by insertion-merge ⇒ O(n log n · L) for "maximum xor of two values in the same subtree",
- DSU-on-tree (Small-to-Large Merging) is the memory-light variant: keep one global array, add/remove subtrees, and exploit the same "light subtrees are touched log times" count,
- polynomial/convolution merging on trees ("count pairs at distance d in each subtree"): merging small-to-large turns an O(n2) DP into O(n log2 n).
| memory | supports | cost | |
|---|---|---|---|
| merge containers (here) | O(n) structures, but allocation-heavy | per-vertex answers for all subtrees | nlog n inserts, simple |
| DSU on tree (sack) | one global array | per-vertex answers, with add/remove semantics; easy to also handle "path to root" | same count, but only O(n) memory and cache-friendly |
| centroid decomposition (Centroid Decomposition) | O(n log n) | pairs across the whole tree with a distance constraint, or global queries | nlog n with different bookkeeping |
- Merging by
map::merge/insert loop without first picking the largest child as the base — then the big map is the destination only by accident; the bound is O(n2) on a path. - Copying instead of moving:
auto m = *child;silently doubles the work; keep pointers (orstd::move) and always leave the biggest child's container in place. - Forgetting that
std::map::mergeis O(size · log) per element, so total is nlog2 n — fine at n ≤ 2×105 (≈ 6×107), fatal at 106.unordered_map+ reserve wins by 3–4×; a global array + DSU-on-tree wins by 10×.