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 instead of .
Space complexity is for the data structures used.