2018/022 Heavy Light Decomposition N개의 정점을 가진 트리가 있다고 하자. 이 때 임의의 두 정점에 대해 이들을 잇는 경로는 O(N)개의 간선을 가진다. Heavy light decomposition(HLD)은 트리의 간선들을 적절히 일자 경로인 “묶음”들로 잘라, 임의의 두 간선 사이 경로를 O(lg N)개의 묶음으로 표현할 수 있게 해 준다. 이것을 세그먼트 트리 등의 일차원 자료 구조와 결합함으로써, 임의의 두 정점 사이의 경로에 대한 연산을 O(lg2N)에 할 수 있다. 간선들을 묶음으로 잘 나누는 방법은 다음과 같다. 1. 임의의 정점을 루트(R)로 지정하여, DFS 탐색을 한다. DFS 탐색을 하면서 각 정점에 대해 다음의 2가지를 계산한다. 1) 루트 노드와의 거리 2) 해당 정점이 루트 노드인 subtree의 크기 2. R.. 2018. 2. 15. ACM-ICPC related materials - hongjun7 팀노트 - ntopia님 팀노트- KAIST 더불어민규당(koosaga, hyea, alex9801) 팀노트- SNU MolaMola(cki86021, dotorya, zigui) 팀노트- csehydrogen님 팀노트- kcm1700님 팀노트- KTH Royal Institute of Technology in Stockholm 대학교 팀노트 - NUS RR Watameda(I_love_Hoang_Yen, flashmt, nguyenhungtam) 팀노트- E-Maxx Algorithms 2018. 2. 14. 이전 1 다음