트리 체인 분할을 이용한 알고리즘 구현 및 응용
개요
트리 체인 분할은 트리를 여러 체인으로 나누어 선형 자료구조를 활용할 수 있도록 하는 기법이다. 이 중 가장 널리 사용되는 방식은 Heavy-Light Decomposition(HLD)이다.
다음과 같은 개념들을 정의한다:
무거운 자식: 특정 노드의 모든 자식 중 서브트리 크기가 가장 큰 자식
가벼운 자식: 무거운 자식을 제외한 나머지 자식들
무거운 간선: 부모와 무거운 자식을 ...
7월 14일 21:25에 게시됨