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