Heavy-Light Decomposition이란 트리를 여러 개의 선형 구조로 분해하여 접근할 수 있게 해주는 기법입니다.먼저 트리 위에서 다음과 같은 쿼리가 주어지는 문제를 생각해 봅시다.정점 i의 가중치를 v로 변경한다.두 정점 간의 경로 상의 정점의 가중치 합을 구한다.당연히? $N \le 100000$ 정도입니다.배열 위에서였다면 바로 신나게 세그먼트 트리를 짰겠지만, 트리 위이다 보니 바로 적용하기는 어렵습니다. 배열에서는 되고, 트리에서는 안 되는 이유는 무엇일까요?당연한 소리지만, 트리는 배열과 달리 비선형구조이기 때문입니다. 그렇다면 이렇게, 트리를 여러 개의 선형 구조로 쪼갠다면 어떨까요?이 경우에는 부분 부분에 대해서는 세그먼트 트리로 관리해줄 수 있겠다는 생각이 듭니다.문제는 이걸 ..
