MakeRoot Operation

Make v the root of its tree (reverse all edges on path from v to current root):

function makeRoot(v)
    access(v)
    // Reverse the auxiliary tree (flip all edges)
    v.reversed := not v.reversed
    pushDown(v)

You use lazy propagation: mark the auxiliary tree as "reversed" without reversing. Push down the reversal flag when accessing children.

function pushDown(v)
    if v.reversed then
        swap(v.left, v.right)
        if v.left then v.left.reversed := not v.left.reversed
        if v.right then v.right.reversed := not v.right.reversed
        v.reversed := false

Time: $O(\log n)$ amortized.