Problem Solving/Data Structure7 트리에서의 Sqrt Decomposition 1) 트리에서 branch를 나눔2) branch를 나누는 기준은 현재 정점에서 자식 노드들이 여럿일 때, 첫 번째 branch는 부모와 x를 잇는 branch와 같다고 하고, 나머지들은 각각 새로운 branch.3) 현재 branch의 길이가 이상이면 cut.그림으로 표현하면 대충 이런 식이 된다.dfs numbering하면서 branch를 나누는 코드는 아래와 같다.cn : branch number, bc : branch에 포함된 노드의 개수, col[x] : x 노드의 branch indexy라는 노드에서 x라는 노드로 올라가면서 일련의 작업을 하는 코드는 아래와 같다. 붉은색 부분에는 branch 전반에 대한 작업, 푸른색 부분에는 특정 노드에 대한 작업을 해주면 된다. 이 코드는 노드와 부모 노.. 2016. 5. 19. Persistent Segment Tree 1. SPOJ 'COT - Count on a tree'2. SPOJ 'MKTHNUM - K-th Number'3. Codeforces Round #140 (Div. 1) Problem E. Noble Knight's Path 2016. 2. 25. 이전 1 2 다음
