hld (1) 썸네일형 리스트형 186. Heavy-Light Decomposition 헤비-라이트 분할(Heavy-Light Decomposition, HLD)는 트리에서 경로와 관련된 다양한 쿼리를 처리하는 테크닉이다. 트리에서 다음과 같은 쿼리를 처리하는 문제를 생각해 보자.$1\ i\ c$: $i$번째 간선의 가중치를 $c$로 바꾼다.$2\ x\ y$: 정점 $x$와 $y$ 사이의 최단 경로가 포함하는 간선들의 가중치의 합을 출력한다.정점이 $n$개인 트리에서 두 정점 사의의 최단 경로는 최대 $(n - 1)$개의 간선을 포함하므로 경로상의 간선을 하나씩 보는 방법은 당연히 너무 느리다. 이 문제점을 해결하기 위해 HLD는 간선을 그룹으로 묶은 다음 그룹을 한 번에 처리할 수 있게 한다. 이때 경로가 너무 많은 그룹을 지나면 간선을 그룹으로 묶는 의미가 없어지므로 어떤 경로를 선택하.. 이전 1 다음
