Pattern Reference
DSU on Tree (Sack)
"Small-to-large merging on trees for offline subtree queries in O(n log n)."
Loading...
Deep Dive Tutorial
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 template
// 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;
}Worked Problems
tree-deciduous
Small-to-large merging key insight: Each element is the "small" one O(log n) times, because each merge at least doubles the size of the set it's in. Total operations = O(n log n).
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."
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."