Merge-by-weight to solve reachability problems in trees and DAGs
There are two (equivalent) ways to fix the argument:


Start by not eliminating duplicates. Then the argument works. Then argue that removing duplicates can only decrease the running time.
Count elements with multiplicity, that is, consider each set $S(x)$ as a multiset.


Both of these arguments require a slight modification of the algorithm: for each vertex $x$, you keep track of the size of the subtree, and use this to select the heaviest child rather than the number of distinct colors.

This argument breaks down for a DAG since a vertex can have multiple parents.