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[v] > size[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. Smaller children merge into the larger one. This keeps total work at O(nlogn) instead of O(n2).
Space complexity is O(n) for the data structures used.