Heavy Light Decomposition

Chat-GPT에게 물어본 Heavy Light Decomposition

 

 

 

 

Heavy Light Decomposition, 줄여서 HLD라고 불리는 알고리즘은 하나의 트리를 여러 개의 서브 트리로 분할하는 방법이다. 이름에 나와있듯이 트리를 무거운(Heavy) 서브트리와 가벼운(Light) 서브 트리로 분할하게 된다. 일반적으로 이 알고리즘은 세그먼트 트리를 트리위에서 적용하기 위해 사용한다. 예를 들자면, 트리위의 어떤 두 정점 $u$와 $v$가 주어졌을 때, 두 정점을 잇는 경로 길이의 합이나 경로 사이에 존재하는 가중치의 최솟값을 여러 번 구하는 문제이다.

 

 

 

 

가장 먼저 1차원 배열 위에서의 세그먼트 트리의 적용이 아닌 트리 위에서의 세그먼트 트리 적용이기 때문에 어떤식으로 정점들을 구성해서 세그먼트 트리를 사용할 수 있도록 변형할지 생각해봐야 한다. 이를 위해 아래와 같이 루트 노드의 번호가 1인 트리가 있다고 해보자.

 

 

 

 

루트가 1인 트리

 

 

 

 

Heavy Light Decomposition에서는 세그먼트트리를 적용시키기 위해 여러 개의 서브 트리로 분리한다고 하였다. 사실 그 기준이 명확하지 않다면 하나의 트리를 여러 개의 서브 트리로 분할하는 방법은 수 없이 많다. HLD의 분할 기준은 서브 트리의 크기이며, 그 크기가 크면 Heavy 서브 트리, 작으면 Light 서브 트리라고 정의한다.

 

 

 

 

HLD는 먼저 무거운 경로와 가벼운 경로를 구분하기 위해서 각 정점을 루트로 하였을 때, 만들어지는 서브트리의 크기를 계산한다고 하였다. 위의 그림에서 6번 정점을 루트 노드로 하는 서브 트리는 (6, 9, 10) 번 정점으로 구성되어 있기 때문에 3이라고 할 수 있는 것이다. 모든 서브 트리의 크기를 계산하여 괄호 안에 표시하면 아래와 같다.

 

 

 

 

 

 

 

 

서브 트리의 크기를 모두 계산하였다면, 이제 그 크기를 사용하여 여러 묶음으로 재분할한다. 이때 이러한 묶음을 하나의 체인이라고 부르게 된다. 1개의 체인을 만들게 되면 DFS와 같은 방식으로 루트 노드로부터 시작하여 가장 무거운 서브 트리를 따라간다. 위의 트리에서는 1번에서부터 시작하여 가장 무거운 것을 따라가면 (1-2-6-9)의 경로를 구할 수가 있다. 이렇게 만들어진 하나의 경로를 체인이라고 부르는 것이다. 만약 자식들의 서브트리 크기가 동일할 경우 어떤 것을 선택해도 무관하다. 

 

 

 

 

DFS에 의해 아직 탐색되지 않은 다른 노드들에 대해서는 해당 정점을 루트 노드로 삼고 같은 과정을 반복해준다. 10번 정점의 경우 방문하지 않은 다른 노드들이 없기 때문에 10번 정점 1개가 하나의 체인을 구성하게 된다. 이런 식으로 모든 노드에 대해 체인을 매겨주면 전반적인 Heavy Light Decomposition의 연산은 종료된다. 아래의 그림은 모든 정점에 대해서 체인으로 분할한 것이며, 같은 색상인 것은 동일한 체인에 속한다는 의미이다.

 

 

 

 

서브트리의 크기를 기준으로 생성한 체인

 

 

 

 

위와 같이 만들게 되면 같은 체인내에서 세그먼트 리를 적용하는 것이다. 예를 들어 $u(6)$와 $v(7)$사이의 간선 가중치의 합을 구하고 싶다면 빨간색 체인에 대해 query(1, 6)과 보라색 체인에 대해 query(4, 7)을 연산하기만 하면 된다. 물론 각 정점에 대한 번호는 다시 매길 필요가 있고, 아래에서 코드로 다시 확인한다.

 

 

 

 

이제 Heavy Light Decomposition은 어떻게 연산을 크게 줄여줄 수 있을지 알아봐야 한다. 어떤 정점 $u$를 시작으로 그의 하위 자식들 중 하나인 $v$로 가는 정점에서 서로 다른 체인의 수는 $\mathcal{O}(\log_2 N)$개가 등장한다. 무거운 간선을 서브트리의 크기가 가장 큰 노드로 정의하였기 때문에 항상 절반 이상은 제외되기 때문이다.

 

 

 

 

 

 

 

 

좀 더 자세히 말하자면, 두 정점 $u$와 $v$의 최소 공통조상(LCA)이 $k$라고 했을 때, 크게 2가지 경로로 나누어 볼 수 있다. 그 두 가지는 $k$에서 $u$로 가는 경로와 $k$에서 $v$로 가는 경로이다. $u$와 $v$는 모두 $k$를 루트로 하는 서브 트리에 포함된 정점이기 때문에 각각 $\mathcal{O}(\log_2 N)$개의 체인을 만나게 된다. 그리고 각 체인에 대해 세그먼트 트리를 적용하게 되면 체인의 개수 $\mathcal{O}(\log_2 N)$에 구간 질의 시간 복잡도인 $\mathcal{O}(\log_2 N)$를 곱하게 되어 최종적인 시간복잡도 $\mathcal{O}((\log_2 N)^2)$를 구할 수 있다.

 

 

 

 

 

 

---

 

 

 

 

13309번: 트리

 

문제는 어떤 두 정점 $u$, $v$가 주어졌을 때, 두 정점이 이어져있는지 확인하는 문제이다. 따라서 트리가 아닌 1차원 배열에서는 구간[$u$, $v$]에 대해 & 연산을 하는 세그먼트 트리를 구성했을 것이다. 이번에는 트리 위에서 HLD를 사용한 후, 구간에 대한 질의를 처리해야 하기 때문에 먼저 서브 트리의 크기를 계산해야 한다.

 

 

 

 

void calc_subtree_size(int here, int level) {
    subtree_size[here] = 1;     // self

    for (int &there : adj[here]) {
        calc_subtree_size(there, level + 1);
        subtree_size[here] += subtree_size[there];

        if (subtree_size[there] > subtree_size[adj[here][0]])
            swap(adj[here][0], there);
    }
}

 

 

 

 

위의 코드를 보면 현재 there의 서브트리 크기가 가장 크다면 here와 연결된 정점 중 가장 앞으로 보내는 것을 알 수 있다. 이 과정은 이후에서 가장 처음으로 연결된 정점이 Heavy 서브 트리임을 보이기 위한 과정이다. 다음은 Heavy와 Light 서브 트리를 사용해서 각 정점들을 체인으로 묶어주는 과정을 구현한 것이다.

 

 

 

 

void heavy_light_decomposition(int here, int depth) {
    HLD_num[here] = HLD_cnt++;
    HLD_depth[here] = depth;

    for (int there : adj[here]) {
    
        // heavy subtree
        if (there == adj[here][0]) {
            HLD_head[there] = HLD_head[here];
            HLD_parent[there] = HLD_parent[here];
            heavy_light_decomposition(there, depth);
        }
		
        // light subtree
        else {
            HLD_head[there] = there;
            HLD_parent[there] = here;
            heavy_light_decomposition(there, depth + 1);
        }
    }
}

 

 

 

 

위 함수에서는 Heavy 서브트리일 경우에는 같은 체인임을 표시하기 위해 현재 체인의 시작점과 현재 체인의 부모 체인을 같은 곳을 가리키도록 설정을 했고, Light 서브 트리일 경우에는 새로운 체인이 시작되는 것이기 때문에 체인의 시작점을 there로 설정하고 그 부모 체인이 here을 가리키도록 만들었다. 또한, 동일한 체인 내에서는 트리의 높이 증가가 없기 때문에 동일한 높이를 전달해준다.

 

 

 

 

이후에는 LCA를 사용하여 질의를 처리해주는 부분만 작성해주면 된다. 먼저 두 정점 $u$와 $v$가 속한 체인의 높이를 같도록 맞춰주고, $u$와 $v$가 동일한 체인에 속하도록 계속 탐색해준다. 마지막 동일 체인내에 속하게 될 경우, 남는 차이에 대해서만 구간 쿼리를 실행하도록 해 주고 최종적인 정답을 출력해주면 된다.

 

 

 

 

// check path that connects b vertex and c vertex
if (HLD_depth[b] > HLD_depth[c]) swap(b, c);

// equalize HLD group depth
while (HLD_depth[b] < HLD_depth[c]) {
    result &= query_tree(1, 1, N, HLD_num[HLD_head[c]], HLD_num[c]);
    c = HLD_parent[c];
}

// to same group
while (HLD_head[b] != HLD_head[c]) {
    result &= query_tree(1, 1, N, HLD_num[HLD_head[b]], HLD_num[b]);
    result &= query_tree(1, 1, N, HLD_num[HLD_head[c]], HLD_num[c]);

    b = HLD_parent[b];
    c = HLD_parent[c];
}

// difference in same group
if (HLD_num[b] > HLD_num[c]) swap(b, c);
result &= query_tree(1, 1, N, HLD_num[b] + 1, HLD_num[c]);

 

 

 

 

---

ChatGPT가 작성한 HLD