Here is the distinct colors implementation:
function distinctColors(n, adj, color):
answer = array of size n
colorSet = array of n empty sets
function dfs(u, parent):
bigChild = -1
bigSize = 0
for v in adj[u]:
if v != parent:
dfs(v, u)
if colorSet[v].size > bigSize:
bigSize = colorSet[v].size
bigChild = v
// Take largest child's set
if bigChild != -1:
swap(colorSet[u], colorSet[bigChild])
// Merge smaller children
for v in adj[u]:
if v != parent and v != bigChild:
for c in colorSet[v]:
colorSet[u].add(c)
// Add current node's color
colorSet[u].add(color[u])
answer[u] = colorSet[u].size
dfs(1, 0)
return answer
Time: . Space: .