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.

If we do not use path compression, we can maintain

`add[v]`

— the sum of all`d`

added to the subtree of`v`

. As the DSU are multiple trees, the weight of a vertex is the sum of`add[p]`

for each parent`p`

. Assume during`merge`

we need to make`parent[a] = b`

. We should make weights in`a`

's subtree relevant by`add[a] -= add[b]`

.If we want to use path compression, implementation becomes a bit more complicated. During

`find(int v)`

operation, we need to return not only the parent of`v`

, but also the sum of`add[u]`

for all`u`

on path to the parent. If we know the sum, we can simply connect`v`

directly to its parent and add the sum to`add[v]`

. Obviously, all weights in`v`

's subtree remain correct.Thanks. This is neat.

Your idea works, but with some minor modifications. For each component, store the vertices in that component as well (the time complexity is still $$$\mathcal{O}(n \log n)$$$ if you use small to large). Then, when merging component $$$X$$$ into component $$$Y$$$, we can first add the lazy value of component $$$X$$$ to all vertices in $$$X$$$, and subtract the lazy value of component $$$Y$$$ from all vertices in $$$X$$$, because when you are asked the value of a vertex $$$v$$$, you will output $$$\text{value}_v + \text{lazy}$$$ (where $$$\text{lazy}$$$ denotes the value of the lazy variable for the component of vertex $$$v$$$), but the lazy increment of the component $$$Y$$$ before you merged $$$X$$$ into it should not have any effect on the current vertex $$$X$$$, so in order to fix this mistake before we commit it, we will subtract $$$\text{lazy}_Y$$$ from the values of all the vertices of $$$X$$$ even before adding them to $$$Y$$$. Similarly, we should add $$$\text{lazy}_X$$$ to the values of all the vertices of $$$X$$$, because you should be adding that, but you don't (because the only thing you add right now is $$$\mathrm{lazy}_Y$$$), so in order to fix that mistake before we commit it, we will add $$$\text{lazy}_X$$$ to the values of all the vertices of $$$X$$$. The time complexity is $$$\mathcal{O}(n \log n)$$$ because of small to large.

Thanks, I didn't think of small-to-large merging.