devmoon

1. 문제 출처 https://www.acmicpc.net/problem/13309 13309번: 트리 표준 입력으로 다음 정보가 주어진다. 첫 번째 줄에는 트리의 정점의 개수와 질의의 개수를 나타내는 두 정수 N과 Q (1 ≤ N, Q ≤ 200,000)가 주어진다. 다음 N-1개의 줄의 i번째 줄에는 정점 i+1의 부 www.acmicpc.net 2. 문제 접근 특정 구간내에 그래프가 연결되어 있는지의 정보를 O(log N)의 시간만에 알아내기 위해 세그먼트 트리 자료구조를 사용해야 했다. 하지만, 트리 구조이기 때문에 트리구조를 체인으로 분할 하는 heavy-light-decomposition 을 적용하여 문제를 해결해야 한다. 먼저 트리의 루트는 항상 1이라고 고정된 상태이기 때문에, 1을 루트로..