Link/Cut Tree (2)

• Link/Cut Tree (1)

앞선 포스트에서 LCT에 대한 기본적인 내용을 다루었는데, 이번 포스트에서는 LCT가 어떻게 활용될 수 있는지 간단하게만 알아보려고 한다. 보충 자료 같은 느낌의 포스트이다.

 

1. Link 연산의 확장

 

원래의 Link 연산은 붙이는 쪽이 represented tree의 루트인 경우에만 가능했다. 그러나 실제로 루트가 아닌 노드를 붙이고 싶을 때도 있을 것이다. 이를 위해서는 represented tree의 루트를 변경하는 작업이 필요하다.

 

어떤 represented tree의 한 노드를 $v$라고 했을 때, access($v$)를 하면 v에서 루트로 연결되는 preferred path가 생긴다는 점은 이전 포스트에서 알아보았다. 그런데 여기서 주목할 점은 이 preferred path의 양끝이 각각 루트와 $v$라는 것이다. 우리는 Splay Tree라는 자료구조로 preferred path(또는 auxiliary tree)를 관리해왔고, access($v$)를 수행하면서 $v$가 이 Splay Tree의 루트에 오게 되므로, 이 Splay Tree를 뒤집어주면 $v$가 가장 왼쪽에 오는 노드가 되면서 전체 represented tree의 루트의 포지션을 갖게 된다.

 

Splay Tree를 직접 뒤집어주면 시간이 너무 오래걸리기 때문에, 우리는 lazy propagation이라는 테크닉을 이용한다. Splay Tree의 lazy propagation에 대해서는 이 블로그에서 볼 수 있다.

 

먼저 자신의 서브트리가 뒤집혔는지 알려주는 값을 노드 구조체에 추가해야 한다.

struct node {
    node *l, *r, *p, *pp;
    bool inv;
};

그리고 propagate을 시키는 함수를 만든다.

void propagate(node *cur) {
    if (!cur->inv) return;
    swap(cur->l, cur->r);
    cur->inv = false;
    if (cur->l) cur->l->inv = !cur->l->inv;
    if (cur->r) cur->r->inv = !cur->r->inv;
}

여기서 swap 함수는 C++ STL의 swap이다. C를 사용하고 싶다면 다음과 같이 한다.

void propagate(node *cur) {
    if (!cur->inv) return;
    node *tmp = cur->l;
    cur->l = cur->r;
    cur->r = tmp;
    cur->inv = false;
    if (cur->l) cur->l->inv = !cur->l->inv;
    if (cur->r) cur->r->inv = !cur->r->inv;
}

Lazy propagation 테크닉에서 항상 주의해야 하는 것은 propagate을 시키는 타이밍이다. 일반적으로 부모에서 자식을 접근할 때 propagate을 해주는데, splay나 rotate 함수와 같은 경우는 조금 애매하다. 그런데 rotate 함수를 자세히 보면 rotate시키려는 노드와 그 노드의 부모를 제외한 나머지 서브트리는 내부적으로 접근하지 않는다는 것을 알 수 있다. 즉 그 노드와 부모의 lazy만 없애주면 안전하다는 뜻이다.

void rotate(node *cur) {
    node *p = cur->p;
    propagate(p);
    propagate(cur);
    if (cur == p->l) {
        if ((p->l = cur->r)) cur->r->p = p;
        cur->r = p;
    } else {
        if ((p->r = cur->l)) cur->l->p = p;
        cur->l = p;
    }
    cur->p = p->p;
    p->p = cur;
    if (cur->p) {
        if (cur->p->l == p) cur->p->l = cur;
        else cur->p->r = cur;
    } else {
        cur->pp = p->pp;
        p->pp = NULL;
    }
}

Splay 함수는 rotate로 구현되어 있으므로 건드리지 않아도 된다. 다만 일반적으로 rotate함수를 직접 부를 일은 많지 않기 때문에 rotate 함수 대신 splay 함수를 직접 고칠 수도 있다. 이 경우 중간 노드를 한 번만 propagate시키면 되기 때문에 성능은 약간 향상된다.

 

추가로, access 함수와 find_root 함수에서도 자식 노드를 접근하기 때문에 역시 propagate을 해주어야 한다.

void access(node *cur) {
    splay(cur);
    propagate(cur);
    if (cur->r) {
        cur->r->pp = cur;
        cur->r->p = NULL;
        cur->r = NULL;
    }
    while (cur->pp) {
        node *pp = cur->pp;
        splay(pp);
        propagate(pp);
        if (pp->r) {
            pp->r->pp = pp;
            pp->r->p = NULL;
        }
        pp->r = cur;
        cur->p = pp;
        cur->pp = NULL;
        splay(cur);
    }
}

node *find_root(node *cur) {
    access(cur);
    while (cur->l) {
        cur = cur->l;
        propagate(cur);
    }
    access(cur);
    return cur;
}

이외에 link 함수, cut 함수 등에서도 자식 노드를 호출하지만, access 함수를 통해 이미 노드에서 propagate이 진행되기 때문에 추가적으로 해줄 필요는 없다.

 

마지막으로 임의의 노드 $v$를 자신이 속한 represented tree의 루트로 만드는 함수를 작성한다.

void make_root(node *cur) {
    access(cur);
    cur->inv = !cur->inv;
}

드디어 Link 연산을 확장할 수 있게 되었다. 이제 임의의 노드를 임의의 다른 트리의 노드로 붙이는 것이 가능하다.

void connect(node *cur, node *nxt) {
    make_root(cur);
    link(cur, nxt);
}

2. 다양한 경로 쿼리

 

이제 LCT를 이용해서 다양한 경로 쿼리를 처리해 보자. 일반적인 트리에서 경로 합 쿼리, 경로 최솟값 쿼리 등은 HLD(Heavy Light Decomposition)를 이용해 어렵지 않게 해결할 수 있었다. 그러나 트리의 Link 연산이나 Cut 연산이 추가될 경우 HLD로는 어렵게 된다.

 

HLD의 기본 아이디어를 떠올려 보자. 어떤 노드에서 루트까지 올라가는 경로를 $O(\log N)$개의 구간으로 쪼갠 뒤, 노드와 조상 노드 사이의 쿼리를 우선적으로 처리하는 것이다. 그러고 나면 임의의 두 노드 사이의 쿼리도 LCA를 구한 뒤 따로따로 처리하는 방법을 사용할 수 있었다.

 

LCT에서도 비슷한 아이디어를 사용할 것이다. 다만 트리가 계속 변하기 때문에 이제 LCA를 $O(\log N)$에 구하는 기존의 방법은 사용할 수 없다. 다른 방법을 생각해야 한다.

 

같은 represented 트리에 속한 두 노드 $v$와 $w$의 LCA를 구해 보자. 일단 다른 연산들이 그렇듯 일단 access 연산은 하고 봐야 한다. access($v$)와 access($w$)를 차례대로 수행하면 무슨 일이 일어날까? access($v$)를 한 뒤에는 $v$에서 루트로 가는 preferred path가 만들어진다. 이후 access($w$)를 하면, $w$에서 루트로 가는 경로가 만들어지면서 원래 $v$와 루트를 잇던 경로에 변화가 생긴다. 이 변화가 생기는 지점이 $v$와 $w$의 LCA라는 것을 알 수 있다.

 

 

좀더 정확하게 이야기하면, access($v$) 직후에는 $v$와 LCA는 (만일 다르다면) preferred edge로 이어져 있겠지만, access($w$)가 수행되면 LCA는 $v$가 포함된 서브트리와의 연결을 끊고 path-parent pointer로 잇게 될 것이다. 예외가 있는데, LCA가 $v$ 자신인 경우이다. 이 경우 $v$는 $w$의 조상노드이므로 $v$에서 루트로 가는 경로는 끊기지 않는다.

 

즉, 위 두 access 연산이 끝난 뒤 $v$가 포함된 auxiliary tree의 path-parent pointer가 존재한다면 그 노드가 LCA이고, 존재하지 않는다면 $v$는 $w$의 조상, 즉 $v$ 자신이 LCA가 된다.

node *lca(node *cur, node *nxt) {
    access(cur);
    access(nxt);
    splay(cur);
    return cur->pp ? cur->pp : cur;
}

이제 준비는 모두 끝났다. 먼저 한 가지 짚고 넘어갈 것이 있는데, 경로 쿼리에는 경로에 있는 노드의 값들에 관한 쿼리와 경로에 있는 간선 값들에 관한 쿼리가 있다. 전자의 경우 별 문제가 없다. 후자의 경우 문제가 될 수 있는데, 노드의 값을 자신과 부모를 잇는 간선의 값으로 설정하면 쉽게 해결될 것 같아 보인다. 그러나 Splay Tree를 뒤집어야 하는 경우 부모자식 관계가 뒤바뀌기 때문에 꽤나 골치가 아프다. 이 경우 간선 중앙에 정점을 추가한 후 그 정점에 값을 적어놓으면 해결 가능하다. (알려주신 koosaga님과 cki86201님 감사합니다.)

 

경로 합 쿼리는 같은 방식으로 처리할 수 있으므로 경로 최솟값 쿼리를 처리해 보자. 우리는 LCA를 구할 수 있기 때문에 노드와 조상 노드 사이의 쿼리만 효율적으로 처리하면 된다. 즉, 노드 $w$의 조상 노드를 $v$라 하고 $v$와 $w$를 잇는 경로에 있는 노드 값들의 최솟값을 구해 보자.

 

먼저 노드 구조체에 자신의 값과 자신의 서브트리의 노드 값들 중 최솟값을 나타내는 변수를 추가하자.

struct node {
    node *l, *r, *p, *pp;
    bool inv;
    int val, min_val;
};

서브트리의 최솟값은 부모자식 관계가 바뀔 때마다 재설정되어야 한다. 이를 위한 reset 함수를 만든다. 이 함수는 rotate, cut, link 함수 마지막 부분에 호출해 주어야 한다.

void reset(node *cur) {
    cur->min_val = cur->val;
    if (cur->l && cur->min_val > cur->l->min_val) cur->min_val = cur->l->min_val;
    if (cur->r && cur->min_val > cur->r->min_val) cur->min_val = cur->r->min_val;
}

void rotate(node *cur) {
    node *p = cur->p;
    propagate(p);
    propagate(cur);
    if (cur == p->l) {
        if ((p->l = cur->r)) cur->r->p = p;
        cur->r = p;
    } else {
        if ((p->r = cur->l)) cur->l->p = p;
        cur->l = p;
    }
    cur->p = p->p;
    p->p = cur;
    if (cur->p) {
        if (cur->p->l == p) cur->p->l = cur;
        else cur->p->r = cur;
    } else {
        cur->pp = p->pp;
        p->pp = NULL;
    }
    reset(p);
    reset(cur);
}

void link(node *root, node *cur) {
    access(root);
    access(cur);
    root->l = cur;
    cur->p = root;
    reset(root);
}

void cut(node *cur) {
    access(cur);
    if (cur->l) {
        cur->l->p = NULL;
        cur->l = NULL;
        reset(cur);
    }
}

노드의 값이 중간중간에 바뀔 수도 있다. 이를 위해 update 함수도 추가한다.

void update(node *cur, int val) {
    access(cur);
    cur->val = val;
    reset(cur);
}

이제 본격적인 path_min 함수를 만들어 보자. 노드 $v$가 $w$의 조상이라는 가정을 했으므로 access($w$)를 수행하면 $v$와 $w$는 하나의 Splay Tree에 모이게 된다. 이제 Splay Tree에서 구간 최솟값 구하기 문제로 바뀐다. 이에 대한 좀더 자세한 설명은 역시 이 블로그를 참고하면 좋다. path_min($v$, $w$) 함수에서는 $v$는 $w$의 조상이고 서로 다르다고 가정한다.

int path_min(node *cur, node *nxt) {
    access(cur);
    access(nxt);
    splay(cur);
    cur->r->p = NULL;
    splay(nxt);
    nxt->p = cur;
    int res = cur->val > nxt->val ? nxt->val : cur->val;
    return nxt->l && res > nxt->l->min_val ? nxt->l->min_val : res;
}

이렇게 경로 최솟값 쿼리 문제도 끝나게 된다. 비슷한 방식으로 Splay Tree의 강력한 기능을 이용해 다양한 경로 쿼리를 처리할 수 있다.

 

LCT는 BOJ에 연습문제가 많지 않다. 다음 문제들은 HLD로 풀리는 문제들이지만, LCT 구현을 제대로 했는지 확인해볼 수 있다.

 

• BOJ 13510: 트리와 쿼리 1
• BOJ 2927: 남극 탐험

* 추가 - 아래 문제집에서 Splay Tree와 Link/Cut Tree를 연습해볼 수 있다. 문제집을 만들고 알려주신 koosaga님 감사합니다.

• BOJ 문제집: Segtrees are too mainstream