Heavy-Light Decomposition 알고리즘

• Heavy-Light Decomposition은 트리의 간선들을 일자 경로로 잘라, 임의의 두 간선 사이 경로를 O(log N)개의 묶음으로 표현할 수 있게 해 준다.

• 이를 세그먼트 트리 등의 자료 구조와 결합함으로써, 임의의 두 정점 사이의 경로에 대한 연산을 O(log^2N)에 할 수 있다.

• 입력으로 주어진 트리에서 두 도시 간의 최대 통행료를 계산하는 문제이다.

• 트리의 간선 가중치를 업데이트하고, 두 도시 간의 최대 가중치를 쿼리하는 연산을 구현해야 한다.