Implementation Pattern

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: $O(n \log n)$. Space: $O(n)$.