Code Structure

Here is the high-level template for small-to-large merging:

function dfs(u, parent)
    for each child v of u
        dfs(v, u)
        if size[set[v]] > size[set[u]] then
            swap(set[u], set[v])
        merge set[v] into set[u]
    process u with combined set

The trick is identifying the largest child and reusing its data structure. Before merging, swap so set[u] always holds the larger set. Then merge every child's set into set[u]. This keeps total work at $O(n \log n)$ instead of $O(n^2)$.

Space complexity is $O(n)$ for the data structures used.