오일러 경로 테크닉 썸네일형 리스트형 BOJ 17429 국제 메시 기구 https://www.acmicpc.net/problem/17429 17429번: 국제 메시 기구 첫째 줄에 N, Q가 주어진다. (1 ≤ N ≤ 500,000, 1 ≤ Q ≤ 100,000) 다음 N-1줄 중 i번째 줄에는 Si, Ei가 주어지며, 이는 금고 Si와 금고 Ei가 연결되어 있다는 뜻이다. (1 ≤ Si, Ei ≤ N) 금고가 연결된 모 www.acmicpc.net 1감은 HLD를 이용한 풀이인데, 서브 트리 쿼리 처리를 어떻게 하는지에서 생각하느라 고생을 많이 했다. 우선 서브 트리 쿼리는 오일로 경로 테크닉을 이용해서 트리를 일자로 늘어뜨리면 해결이 된다. 트리를 순회(preorder traverse)하면서 노드의 발견 시각과 종료시각을 기록한다. 노드의 발견시각을 그 노드의 인덱스로 .. 더보기 이전 1 다음