Pattern Guide
DSU on Tree (Small-to-Large)
"Heavy child inherits parent's data. Light children merged small-to-large. O(n log n)."
DSU on Tree (also called "small-to-large merging" or "Sack") efficiently answers subtree queries by merging smaller sets into larger ones. The heavy child inherits the parent's data structure; light children are processed and merged in. Each element is merged O(log n) times total, giving O(n log n) overall. Classic applications: count distinct values in subtree, most frequent element in subtree, frequency queries.
Problems you can solve with this pattern
4 problems · click any to start solving
// DSU on Tree (Sack algorithm)
// Counts distinct values in subtrees
function dsuOnTree(n, edges, vals) {
const adj = Array.from({length: n}, () => []);
for (const [u, v] of edges) { adj[u].push(v); adj[v].push(u); }
const sz = new Array(n).fill(1), heavy = new Array(n).fill(-1);
// DFS1: compute subtree sizes and heavy children
function dfs1(u, p) {
for (const v of adj[u]) {
if (v === p) continue;
dfs1(v, u);
sz[u] += sz[v];
if (heavy[u] === -1 || sz[v] > sz[heavy[u]]) heavy[u] = v;
}
}
const freq = new Map(); // current multiset
let distinct = 0;
const answers = new Array(n);
function add(val) {
const c = (freq.get(val) || 0) + 1;
freq.set(val, c);
if (c === 1) distinct++;
}
function del(val) {
const c = freq.get(val) - 1;
freq.set(val, c);
if (c === 0) { freq.delete(val); distinct--; }
}
function addSubtree(u, p) { add(vals[u]); for (const v of adj[u]) if (v !== p) addSubtree(v, u); }
function delSubtree(u, p) { del(vals[u]); for (const v of adj[u]) if (v !== p) delSubtree(v, u); }
function dfs2(u, p, keepData) {
// Process light children (erase after)
for (const v of adj[u]) {
if (v === p || v === heavy[u]) continue;
dfs2(v, u, false);
}
// Process heavy child (keep data)
if (heavy[u] !== -1) dfs2(heavy[u], u, true);
// Add light subtrees + current node
for (const v of adj[u]) {
if (v === p || v === heavy[u]) continue;
addSubtree(v, u);
}
add(vals[u]);
answers[u] = distinct; // answer query for node u's subtree
if (!keepData) delSubtree(u, p);
}
dfs1(0, -1);
dfs2(0, -1, false);
return answers;
}DSU on Tree works as follows: for each node, process all light children (adding their subtree nodes, answering queries, then erasing them), then process the heavy child WITHOUT erasing, and finally add the current node. The heavy child's data persists, so you only pay the cost for light subtree nodes. Since each node is a "light child" O(log n) times, total work is O(n log n).
// DSU on Tree (Sack algorithm)
// Counts distinct values in subtrees
function dsuOnTree(n, edges, vals) {
const adj = Array.from({length: n}, () => []);
for (const [u, v] of edges) { adj[u].push(v); adj[v].push(u); }
const sz = new Array(n).fill(1), heavy = new Array(n).fill(-1);
// DFS1: compute subtree sizes and heavy children
function dfs1(u, p) {
for (const v of adj[u]) {
if (v === p) continue;
dfs1(v, u);
sz[u] += sz[v];
if (heavy[u] === -1 || sz[v] > sz[heavy[u]]) heavy[u] = v;
}
}
const freq = new Map(); // current multiset
let distinct = 0;
const answers = new Array(n);
function add(val) {
const c = (freq.get(val) || 0) + 1;
freq.set(val, c);
if (c === 1) distinct++;
}
function del(val) {
const c = freq.get(val) - 1;
freq.set(val, c);
if (c === 0) { freq.delete(val); distinct--; }
}
function addSubtree(u, p) { add(vals[u]); for (const v of adj[u]) if (v !== p) addSubtree(v, u); }
function delSubtree(u, p) { del(vals[u]); for (const v of adj[u]) if (v !== p) delSubtree(v, u); }
function dfs2(u, p, keepData) {
// Process light children (erase after)
for (const v of adj[u]) {
if (v === p || v === heavy[u]) continue;
dfs2(v, u, false);
}
// Process heavy child (keep data)
if (heavy[u] !== -1) dfs2(heavy[u], u, true);
// Add light subtrees + current node
for (const v of adj[u]) {
if (v === p || v === heavy[u]) continue;
addSubtree(v, u);
}
add(vals[u]);
answers[u] = distinct; // answer query for node u's subtree
if (!keepData) delSubtree(u, p);
}
dfs1(0, -1);
dfs2(0, -1, false);
return answers;
}DSU on Tree vs Small-to-Large:
- DSU on Tree (Sack): explicit heavy-light decomposition, O(n log n)
- Small-to-large: merge data structures explicitly, O(n log²n) if data structure ops are O(log n)
What structures can be merged small-to-large:
- Sets, multisets, sorted arrays
- Frequency maps
- Segment trees (merging = O(n log n) total)
When to use: Subtree aggregate queries where merging is the bottleneck. Particularly when query = "count distinct values in subtree."