Heavy Light Decomposition

N개의 정점을 가진 트리가 있다고 하자. 이 때 임의의 두 정점에 대해 이들을 잇는 경로는 O(N)개의 간선을 가진다. Heavy light decomposition(HLD)은 트리의 간선들을 적절히 일자 경로인 “묶음”들로 잘라, 임의의 두 간선 사이 경로를 O(lg N)개의 묶음으로 표현할 수 있게 해 준다. 이것을 세그먼트 트리 등의 일차원 자료 구조와 결합함으로써, 임의의 두 정점 사이의 경로에 대한 연산을 O(lg2N)에 할 수 있다.
간선들을 묶음으로 잘 나누는 방법은 다음과 같다.

1. 임의의 정점을 루트(R)로 지정하여, DFS 탐색을 한다.
DFS 탐색을 하면서 각 정점에 대해 다음의 2가지를 계산한다.
1) 루트 노드와의 거리
2) 해당 정점이 루트 노드인 subtree의 크기

2. R에서 DFS 탐색을 한 번 더 하면서 간선들을 chain 묶음으로 분류한다.
어떤 정점 X에 대해 자식 노드 중 subtree의 크기가 가장 큰 노드(Y0) 쪽으로 chain을 이어준다. Y0를 제외한 자식 노드들에는 새로운 chain 번호를 부여한다.
Y0 쪽으로 chain을 이어주면서 다른 자식 노드들에 앞서 우선적으로 DFS 탐색을 수행하며 DFS numbering을 해준다. 이렇게 하면 모든 chain이 연속한 DFS number를 가지는 정점들로만 구성됨을 알 수 있다.
각 chain의 머리에 해당하는 정점의 DFS number와 꼬리에 해당하는 정점의 DFS Number 또한 계산해두면 유용하다.

chain을 subtree의 크기가 가장 큰 자식노드 쪽으로 이어주었기 때문에, 어느 두 정점 사이를 잇는 경로 상에 O(lg N)보다 많은 K개의 chain을 만난다고 가정하면, 전체 정점의 개수가 N개를 넘어버리는 모순이 유도되기 때문에 가정이 성립하지 않음을 알 수 있다. 1+2+4+8+….+2K > N.
(subtree의 크기가 가장 큰 자식 노드가 여럿일 경우에도 귀납적으로 증명이 된다.)
위의 방법을 구현해보면 다음 코드처럼 30줄이 되지 않음을 알 수 있다.
아래 코드에서 chain의 새로운 번호로, 해당 정점의 번호를 지정해주었다. 따라서 각 chain의 머리에 해당하는 정점의 번호가, chain의 번호와 같게 구현되어 있다.

HLD를 수행한 트리에서, 임의의 두 정점 X, Y의 Lowest Common Ancestor를 구하는 방법은 다음과 같다.

while ( X와 Y가 다른 chain에 속해 있다 ) {
    X1 = X가 속한 chain의 가장 위에 있는 정점
    Y1 = Y가 속한 chain의 가장 위에 있는 정점
    if ( Lev[X1] > Lev[Y1] ) X = Par[X1]
    else Y = Par[Y1]
}
LCA = X와 Y 중 루트 노드에 더 가까운 정점

트리 경로 상에 일정한 값을 더한다거나, 최댓값 혹은 최솟값을 구하는 등의 연산은 DFS number를 기준으로 Segment Tree로 구현할 수 있고, 위의 의사코드에서 어떤 정점 X의 DFS number부터 X가 속한 chain의 머리 부분의 DFS number까지 수행하는 쿼리로 수행하면 된다.