경로 및 서브트리 갱신을 위한 Heavy-Light Decomposition 활용
이 문제는 트리 위에서 두 가지 쿼리를 처리해야 하는 고전적인 HLD(Heavy-Light Decomposition) 적용 문제입니다. 노드 구간의 지연 갱신과 서브트리 합 질의를 효율적으로 해결해야 합니다.
핵심 개념
트리를 선형 구조로 변환하여 구간 자료구조를 적용하는 것이 핵심입니다. DFS 순서를 활용하면 서브트리를 연속된 구간으로 표현할 수 있으며, Heavy-Light Decomposi ...
8월 1일 09:05에 게시됨