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: . Space: .