Small to Large Techniques
Small to large is a general merging rule: whenever two containers must be combined, move the smaller one into the larger one. This simple choice turns many apparently quadratic solutions into or solutions.
It is useful with sets, maps, frequency tables, component data, subtree answers, and offline query processing.
We have a rooted tree. Every vertex has a color. For each vertex , find the number of distinct colors in the subtree of .
A direct DFS can build a set for every subtree. If we always insert every child set into the current set without choosing the direction carefully, a long chain can repeatedly copy almost the whole subtree and take .
Suppose we must merge sets and . If is smaller, swap them, then insert every element of into . The result is the same, but only elements from the smaller set move.
Why is this fast? Whenever an element moves, it enters a container at least twice as large as its previous container. A container cannot grow beyond , so one element moves at most times.
This doubling argument is the heart of the technique. It works for any mergeable container where choosing the destination does not change the meaning of the answer.
For each vertex, maintain a set containing all colors in its subtree. Process children first. Before merging a child set into the current vertex set, compare their sizes and swap if needed.
Algorithm:
With set, each insertion costs and each color is moved times, giving . With hash tables, the expected time is often .
Imagine every subtree carrying a bag of colors. A small bag is poured into a big bag. We never pour a big bag into a small one, because that would make many elements travel again.
The swap exchanges the containers, not the meanings of the vertices. The child answer was already saved before the swap, so its set may safely be reused.
The input contains the tree and colors. The tree is rooted at vertex .
set: each insertion has a logarithmic cost.set1. Start a DFS from the root.
2. At vertex v:
1. Insert color[v] into its set.
2. Process every child u.
3. If set[v] is smaller than set[u], swap the two sets.
4. Insert every color from set[u] into set[v].
5. Clear set[u], because all its information is now inside set[v].
6. Set answer[v] = size of set[v].
3. Print all answers.
#include <bits/stdc++.h>
#define fi first
#define se second
using namespace std;
const int N = 200200;
int n;
int color[N], ans[N];
vector<int> g[N];
set<int> st[N];
void dfs(int v, int p) {
st[v].insert(color[v]);
for (int u : g[v]) {
if (u == p) {
continue;
}
dfs(u, v);
if (st[v].size() < st[u].size()) {
swap(st[v], st[u]);
}
for (int x : st[u]) {
st[v].insert(x);
}
st[u].clear();
}
ans[v] = st[v].size();
}
void solve() {
cin >> n;
for (int i = 1; i <= n; i++) {
cin >> color[i];
}
for (int i = 1; i < n; i++) {
int v, u;
cin >> v >> u;
g[v].push_back(u);
g[u].push_back(v);
}
dfs(1, 0);
for (int i = 1; i <= n; i++) {
cout << ans[i] << " \n"[i == n];
}
}
int32_t main() {
ios::sync_with_stdio(false);
cin.tie(nullptr);
cout.tie(nullptr);
solve();
return 0;
}