Here is another problem which can be solved using a similar merge technique. My solution.

Btw, your implementation for the original problem is not completely correct. While you need to travel the whole map of each node your solution become O(n^2logn)