Original Question here.
The question is as follows: Let all elements in sets have some weights. Add the following operations to Disjoint Sets: 1) increase all weights in the given set by d, 2) find the current weight of the element x.
I thought of maintaining a lazy value on the representative node of the component for Query 1. For query 2, we can add the weight of node x + accumulated weight on the representative node. However, I am unable to think of how to maintain this when I merge two components. The already accumulated weights on one node needs to get transferred to it's current subtree and not the future one.
I thought of not using Path Compression at all, and then we will calculate the weight of node x as the sum of weights of all its parent but again I am not sure what to do when we perform the merge operation.
