Remove specific edge from ST (link-cut) tree

Question

ST (or link cut) trees are a special kind of trees used for dynamic graph algorithms. They support the following operations in logarithmic time:

• CUT(v) Deletes the edge from v to its parent
• JOIN(v, w) Where v is a root vertex, assigns parent(v) ← w (makes v a child of w)
• FIND_ROOT(v) Returns the root of the tree containing v

My question here is how to delete an arbitrary edge (u, v) from the tree, and what would be its complexity? If it is too complex or unfeasible to do that, can you point me to an algorithm ((pseudo)code) for the fully dynamic unweighted undirected graph connectivity problem. If it is of any help, the degree of every edge is guaranteed to be at most 2 at any point of the algorithm.

I've read quite a few papers on the topic but in almost all of them the authors only give us very high level descriptions of these structures, in the form of theorems.

Answer 1

For any edge $(u,v)$ either $u$ is $v$'s parent or vice versa. So you just call CUT for "deeper" vertex.

UPD: To determine which vertex is deeper you can use Access($v$). If after this operation $u$ is a rightmost node of $v$'s left (path)subtree, then $u$ is $v$'s parent and you can call CUT($v$) (or just $\mbox{left}(v) \gets \mbox{Null}$ because Access($v$) was called before). Else you call CUT($u$).