경로 및 서브트리 갱신을 위한 Heavy-Light Decomposition 활용
이 문제는 트리 위에서 두 가지 쿼리를 처리해야 하는 고전적인 HLD(Heavy-Light Decomposition) 적용 문제입니다. 노드 구간의 지연 갱신과 서브트리 합 질의를 효율적으로 해결해야 합니다.
핵심 개념
트리를 선형 구조로 변환하여 구간 자료구조를 적용하는 것이 핵심입니다. DFS 순서를 활용하면 서브트리를 연속된 구간으로 표현할 수 있으며, Heavy-Light Decomposi ...
8월 1일 09:05에 게시됨
NOIP 모의 경연 1 회 후기 및 문제 분석
서론
올해도 역시 AC 자동기 문제에서 고배를 마셨다. 사실 ST3 문제에서 AC 자동기 접근 방식이 매우 자연스럽게 떠올랐고, 절반 정도는 해결했음에도 불구하고 T4 문제로 방향을 틀어 결국 300점 이상의 고득점을 놓치고 말았다. Trie 트리와 실패(Fail) 포인터가 어쩌면 운명적인 조합처럼 느껴지지 않는가? 최종 결과는 100 + 100 + 20 + 0으로 아쉬운 성적으로 마무리 ...
7월 3일 18:18에 게시됨