I have read this on various posts on Codeforces (some very old, some a little more recent) that Amortized Complexity algorithms lose this property when we perform rollbacks. An example: Comment by Retrograd here.

Rollbacks here means storing changes in some data structure and reversing back to the previous state until required.

While I would love a general answer, I am specifically asking for DSU Rollbacks with Path Compression. Is there any particular reason why it should not work? Intuitively I'm performing just as many operations as I did to reach the new state to go back to the old state.

Also some might state that between a Union and the time we rollback to it, there could be a 100 odd queries which would cause path compression. We lose all this data after rollback and have to recompute them for further queries. However I am not sure if this realllly messes up the complexity. Every query is still the same complexity?! Notice that this is rollbacks and not persistent DSU.

While I know union by size vs path compression is just NlogN vs N*alpha, there's this particular problem that had me interested: Codechef — Chef and Graph Queries. I had implemented an NRootNLogN solution with Mo's and DSU Rollbacks with Union by Size which TLE's despite many small optimizations. On the other hand the tester's solution does path compression with rollbacks. (Note I am aware a Mos+DSU solution without any rollbacks also exists, and it is quite beautiful but the question isn't about that).

I am attaching a rough implementation just for the idea:

int find(int x)
{
	if(par[x]==x) return x;
	stk.push(mp(x, par[x]));
	par[x]=find(par[x]);
	return par[x];
}
void uni(int x, int y)
{
	x=find(x); y=find(y);
	if(sz[y]>sz[x])
	{
		swap(x, y);
	}
	sz[x]+=sz[y];
	sz[y]=0;
	sizes.push(stk.size());
	stk.push(mp(y, par[y])); //also push the y component size here
	par[y]=x;
}
void rollback()
{
	int lstsz=sizes.top();
	stk.pop();
	while(stk.size()>lstsz)
	{
		par[stk.top().first]=stk.top().second;
		stk.pop();	
	}//also adjust the y component size here
}

To sum it up, if we are really just reversing X operations, why would the complexity be more than 2*X, why do Amortized Algorithms fail on rollbacks. Thanks.