Access Is Everything

What does access(x) do in a link/cut tree, and why does every other operation quote the same complexity?

A

It compresses the virtual edges above xx into a single parent pointer, at O(α(n))O(\alpha(n)) amortized. link, cut, findroot and split are thin wrappers around it, so they inherit that bound.

B

It makes the root-to-xx path a single preferred path held in one splay tree, at O(log⁡n)O(\log n) amortized. link, cut, findroot and split are thin wrappers around it, so they inherit that bound.

C

It rebuilds the heavy light decomposition of the current tree into one balanced structure, at O(log⁡2n)O(\log^2 n) amortized. link, cut, findroot and split are thin wrappers around it, so they inherit that bound.

D

It rotates xx to the root of the represented tree, held in one splay tree, at O(log⁡n)O(\log n) amortized. link, cut, findroot and makeroot become free once it has run, so they inherit no further cost.