Here is the small-to-large merging pattern:
function dsuOnTree(n, adj, color):
answer = array of size n
sets = array of n empty sets
function dfs(u, parent):
sets[u].add(color[u])
biggestChild = -1
biggestSize = 0
for v in adj[u]:
if v == parent:
continue
dfs(v, u)
if sets[v].size > biggestSize:
biggestSize = sets[v].size
biggestChild = v
// Take the largest child's set
if biggestChild != -1:
swap(sets[u], sets[biggestChild])
// Merge smaller children into u's set
for v in adj[u]:
if v == parent or v == biggestChild:
continue
for item in sets[v]:
sets[u].add(item)
sets[u].add(color[u])
answer[u] = sets[u].size
dfs(root, -1)
return answer
Time: . Space: .