[Link Cut Tree] 6. 간선 쿼리

 앞에서는 정점의 쿼리에 대해서 다루었는데, 이제는 간선의 쿼리를 다룹니다.

간선의 쿼리를 하는 방법은 2가지가 있습니다.

1)

 자주 사용하는 방법으로, 간선의 값을 그 간선 중 자식 노드의 값으로 저장합니다.

점 $x$와 $y$ 사이의 쿼리를 구할 때, $lca(x, y)$의 값은 포함되지 않음에 주의합시다.

int query(node * x, node * y) {
    node * p = lca(y, x);
    int sum = 0;
    access(x);
    splay(p);
    if (p->r) sum += p->r->sum;
    access(y);
    splay(p);
    if (p->r) sum += p->r->sum;
    return sum;
}

이 방법의 결정적인 단점은 루트를 바꿀 수 없다는 것입니다.

Link/Cut Tree는 두 점중 하나가 루트여야 연결이 가능하기 때문에 루트를 바꾸지 못하면 연산에 제한이 생깁니다.

2)

 모든 간선을 하나의 정점으로 만듭니다.

기존의 정점들의 값은 항등원을 주고, 앞 글에서 한 것과 같이 쿼리를 하면 간선의 쿼리를 구할 수 있습니다.

 이제 Link/Cut Tree로 간선이 추가되는 연산이 있는 Dynamic MST(최소비용신장트리) 문제를 해결할 수 있습니다.

초기 상황에서 크루스칼 등으로 MST를 구합니다.

이제 간선 $(x, y)$가 추가되면 사이클이 생기는데, 이것은 $x$와 $y$의 기존 경로에 새로운 간선을 추가한 것과 같습니다.

$x$와 $y$의 경로에서 가장 비싼 간선을 찾고, 그 간선의 비용이 새로 추가된 간선의 비용보다 크면 간선을 바꾸고, 아니면 새로운 간선을 버립니다.

간선이 추가될 때마다 $O(logN)$의 시간에 새로운 MST를 찾을 수 있게 됩니다.