[Link Cut Tree] 2. 연산 (1)

void link(node * x, node * y) {
    access(x); access(y);
    x->l = y;
    y->p = x;
    update(x);
}

Link 연산은 x의 부모를 y 노드로 만드는 연산입니다.

Link 연산을 할 때 x는 한 트리의 루트여야 하고, x와 y는 다른 트리에 있어야 합니다.

x와 y에 모두 Access하면, x와 y가 각각의 Splay Tree에서 루트가 됩니다.

x->l (x가 트리의 루트이므로 NULL)을 y로 만들어주면 y가 x의 부모가 됩니다.

여기서 포인터를 끊거나 붙일 때는 항상 update를 해주어야 합니다.

void cut(node * x) {
    access(x);
    x->l->p = 0;
    x->l = 0;
    update(x);
}

Cut 연산은 x와 x의 부모 사이의 연결을 끊는 연산입니다.

이 때 x는 트리의 루트가 아니여야 합니다.

x에 Access하고, x와 x->l (x의 모든 조상들)을 끊으면 됩니다.

node * lca(node * x, node * y) {
    access(x);
    return access(y);
}

x와 y의 LCA를 구하기 위해서 x와 y는 다른 트리에 있어야 합니다.

일단 x에 Access 합시다.

그러면 x와 x의 조상들(루트를 포함)이 하나의 Path에 묶이게 됩니다.

그리고 y에 Access하면 Access 함수의 반환값이

"루트가 포함되던 Path에서 y와 가장 가까운 노드"

인데, x와 x의 조상들이 루트와 같은 Path에 묶여있으므로 그 중에 y와 가장 가까운 노드인 x와 y의 LCA가 반환됩니다.