https://mirror.codeforces.com/edu/course/2/lesson/7/1/practice/contest/289390/problem/C
in this problem if i used path compression get wrong answer and accept without path compression can any one explain why
this code that get wrong answer https://mirror.codeforces.com/edu/course/2/lesson/7/1/practice/contest/289390/submission/132622662
this code that get accept https://mirror.codeforces.com/edu/course/2/lesson/7/1/practice/contest/289390/submission/132624996
If you could give an test , that would be great
The whole idea of this problem is that normal path compression doesnt work and union by size does (or maybe using nothing works as well because of weak test cases).
Path compression doesnt just magically make the complexity better. Suppose we have something like this:
When we call merge on 3 and 4 without path compression, we get this:
Then if we call "get" on 3, we would get the right answer, 10 — 20 + 40 = 30.
However, this is what happens when we find the leader for 3 and merge later:
All the relations between the nodes are lost, and now the 10 points from 2 aren't count for the answer, giving 20 instead of 30. This gets very wrong very quickly.
If you really want a solution with path compression, here is mine. Im basically updating the information of the nodes while doing the path compression to prevent this from happening