# 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;
}


• I don't understand what your question is. If you are asking how to make a mathematical definition of cut(u,v), you can define a term in any way you want. Only you can tell us what definition you want to use. If your question is about how to implement something in C code, that is off-topic here. Coding questions and programming questions are off-topic here, so we ask that you eliminate all C code and replace it with concise pseudocode and ideas. – D.W. May 16 '17 at 22:14
• First of all, how to determine if a pair (u,v) is an edge of the represented tree. And if it is the case, how to cut this edge. Here code and pseudo-code are essentially the same – Leafar May 16 '17 at 22:34
• I don't think you should assume that everyone here reads C code. We already have a separate site (Stack Overflow) for implementation questions and questions about code. – D.W. May 16 '17 at 22:35

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.