The traditional implementation of union find tree (aka disjoint set) utilizes rank compression — this is the code with it.

int parent[1000], rank[1000];

int find(int x){
    return parent[x] = (parent[x] == x ? x : find(parent[x]));
}

void Union(int p, int q){
    p = find(p);
    q = find(q);
    if(rank[p] < rank[q]) parent[p] = q;
    else parent[q] = p;
    if(rank[p] == rank[q]) rank[p]++;
}

But in competitive programming, I found out that the rank compression was useless. Without rank compression, the code was shorter, and even the program ran faster. This is my implementation without rank compression.

int parent[1000];

void Union(int p, int q){ parent[find(p)] = find(q); }

and for some cases, I found implementing rank compression is quite hard (maybe impossible).

I will give you a sample problem : "Given a tree T, you should process Q queries — "paint the edge's value into x (>0) from path s to e".

I reversed the query, broke down the path s — e to s — LCA(s,e) — e, and used this algorithm to paint the tree. (root_val[s] : value of edge s — parent(s), dep[s] = depth of s. nxt[s] = parent(s))

int paint(int s, int e, int x){  
    if(dep[s] <= dep[e]) return s;  
    if(!root_val[s]) root_val[s] = x;  
    return nxt[s] = paint(nxt[s],e,x);  
}

All of those program ran very fast in practice, but I was curious about the worst-case runtime of such path compression without ranks, so I googled for a while but didn't find any answer. Here's my question:

1. Does the path compression runs in (amortized) sublinear time?
2. If it doesn't, is there any counterexamples for that?