Implementation Tips

Here is the complete implementation pattern:

function smallToLargeMerge(n, adj):
    subtreeSize = array of size n

    // Pass 1: Compute subtree sizes
    function computeSize(u, parent):
        subtreeSize[u] = 1
        for v in adj[u]:
            if v != parent:
                computeSize(v, u)
                subtreeSize[u] = subtreeSize[u] + subtreeSize[v]

    // Pass 2: Small-to-large merge
    function merge(u, parent, data):
        bigChild = -1
        for v in adj[u]:
            if v != parent:
                if bigChild == -1 or subtreeSize[v] > subtreeSize[bigChild]:
                    bigChild = v

        // Process small children first
        for v in adj[u]:
            if v != parent and v != bigChild:
                merge(v, u, newData)
                // Merge newData into data

        // Process big child last (take its data)
        if bigChild != -1:
            merge(bigChild, u, data)

        // Add current node's contribution
        addToData(u, data)

    computeSize(root, -1)
    merge(root, -1, emptyData)

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