Introduction 트리를 분할하는 방법으로는 대표적으로 Centroid Decomposition과 Heavy-Light Decomposition이 있다. Centroid Decomposition의 경우, 주로 트리에서 분할정복을 위해 이용되며, Heavy-Light Decomposition은 우리가 다루기 더 쉬운 형태인 선형 배열의 형태로 트리를 바꾸어 문제를 해결하기 위하여 사용한다. 이번 포스팅에서는 Heavy-Light Decomposition을 다룬다. Heavy-Light Decomposition Heavy-Light Decomposition(HLD)는 트리의 정점을 여러 경로의 집합으로 나누는 방법이다. HLD를 수행하기 위해서 일단 임의의 정점의 트리의 루트로 잡는다. 이후, 루트에서..
