Small-to-Large Merging — Trees + Sets

The problem pattern

Given tree with colors, for each node output distinct colors in subtree.

The technique

Set dfs(int u) {
  Set merged = new HashSet<>();
  merged.add(color[u]);
  for (int v : children[u]) {
    Set child = dfs(v);
    if (child.size() > merged.size()) { swap child and merged; }
    merged.addAll(child);
  }
  answer[u] = merged.size();
  return merged;
}

Amortized analysis

Each element moved only when it's in the smaller set. Its position doubles → O(log N) moves total → O(N log² N) with hash sets.

Applications

Distinct colors in subtree. Subtree count queries. Offline range queries.