Codeforces: Need help understanding smaller to larger merge trick

In problem E’s editorial here https://codeforces.com/blog/entry/21827, I have a doubt in the line every time when vertex v will be moved from one map to another the size of the new map will be at least two times larger .

If the maps are for example [a -> p, b -> q, c -> r] and [a -> x, b->y, c->z] then the resulting map should be [a->p+x, b->q+y, c->r+z], then isn’t it the same size?

The maps have some keys corresponding to some vertices. They generally don’t match for two vertices, hence neither ‘a’,‘b’,‘c’ is in both maps. Now the size trivially doubles if you club smaller to larger. Although in some problems the key maybe same for two vertices it is trivial to realize that this only reduces time complexity as the size of the maps as you just pointed out will be lower than expected, which in turn means lower merge time in the upper levels on recursion. So yeah all keys for vertices being different is the worst case analysis.

You can read the blog on DSU on tree to understand this trick. Its pretty common and similar to the idea used to get O(n log n) DSU, double the size when you process anything, this way you’ll only process it O(log n) times.

CF is down rn so can’t really see the exact context of your qn.