# Link-cut trees: how to code cut(u,v)

In most bibliography, only cut(v) is defined. More properly, only cut(v,v.parent) is defined, where (v,v.parent) is an edge in the represented tree.

The pseudo-code and code for this is:

cut(x):
access(x);
parent(left(x)) = null
left(x) = null

void cut(Node *x){
access(x);
x->left->parent = 0;
x->left = 0;
}


How can we define cut(u,v) for an arbitrary (u,v)?

I.e. how can we code cut(u,v) in such a way that

1. If (u,v) is not an edge in the represented tree, then do nothing;

2. If (u,v) is an edge of the represented tree, cut the edge in the represented tree.

The following function may help, it determines the root of the represented tree that contains the node x.

root(x):
access(x)
while(left(x) =/= null)
x = left(x)
splay(x)

LCT *root(LCT *x){
access(x);
while((*x).left != NULL){
x = (*x).left;
}
splay(x);
return x;
}


The function $cut(v)$ is only defined for cutting $v$ from its parent for a reason, because this is the only possibility. The represented tree is first and foremost a Tree. By definition, edges will only exist from a parent to a child. Therefore, the only edge you would ever need to cut is from parent to child.