Lomsat gelral - Implementation

Here is the small-to-large merging for dominant colors:

function lomsatGelral(n, adj, color):
    answer = array of size n
    freq = array of n empty maps
    subtreeSize = array of size n

    function computeSizes(u, parent):
        subtreeSize[u] = 1
        for v in adj[u]:
            if v != parent:
                computeSizes(v, u)
                subtreeSize[u] = subtreeSize[u] + subtreeSize[v]

    function dfs(u, parent):
        bigChild = findBiggestChild(u, parent)

        for v in adj[u]:
            if v != parent and v != bigChild:
                dfs(v, u)

        if bigChild != -1:
            dfs(bigChild, u)
            swap(freq[u], freq[bigChild])

        // Merge smaller children
        for v in adj[u]:
            if v != parent and v != bigChild:
                for (c, cnt) in freq[v]:
                    freq[u][c] = freq[u][c] + cnt

        freq[u][color[u]] = freq[u][color[u]] + 1

        // Find sum of max-frequency colors
        maxFreq = 0
        sum = 0
        for (c, cnt) in freq[u]:
            if cnt > maxFreq:
                maxFreq = cnt
                sum = c
            else if cnt == maxFreq:
                sum = sum + c

        answer[u] = sum

    computeSizes(root, -1)
    dfs(root, -1)
    return answer

Time: $O(n \log n)$. Space: $O(n)$.