devmoon

Heavy Light Decomposition, 줄여서 HLD라고 불리는 알고리즘은 하나의 트리를 여러 개의 서브 트리로 분할하는 방법이다. 이름에 나와있듯이 트리를 무거운(Heavy) 서브트리와 가벼운(Light) 서브 트리로 분할하게 된다. 일반적으로 이 알고리즘은 세그먼트 트리를 트리위에서 적용하기 위해 사용한다. 예를 들자면, 트리위의 어떤 두 정점 $u$와 $v$가 주어졌을 때, 두 정점을 잇는 경로 길이의 합이나 경로 사이에 존재하는 가중치의 최솟값을 여러 번 구하는 문제이다. 가장 먼저 1차원 배열 위에서의 세그먼트 트리의 적용이 아닌 트리 위에서의 세그먼트 트리 적용이기 때문에 어떤식으로 정점들을 구성해서 세그먼트 트리를 사용할 수 있도록 변형할지 생각해봐야 한다. 이를 위해 아래와 같이 ..