BOJ 17429 국제 메시 기구

https://www.acmicpc.net/problem/17429

17429번: 국제 메시 기구

1감은 HLD를 이용한 풀이인데, 서브 트리 쿼리 처리를 어떻게 하는지에서 생각하느라 고생을 많이 했다.

우선 서브 트리 쿼리는 오일로 경로 테크닉을 이용해서 트리를 일자로 늘어뜨리면 해결이 된다. 트리를 순회(preorder traverse)하면서 노드의 발견 시각과 종료시각을 기록한다. 노드의 발견시각을 그 노드의 인덱스로 이용하면, 어떤 노드를 루트로 하는 서브 트리에 속한 모든 노드의 번호는 루트의 발견시각과 종료시각 사이에 있고, 어떤 노드의 발견시각과 종료시각에 해당하는 노드는 모두 그 노드를 루트로 하는 서브트리에 속한다.

이제 HLD를 하면서 만든 세그먼트 트리들과 오일러 경로 테크닉을 이용하여 만든 세그먼트 트리 간의 값을 상호 업데이트하는 방법을 생각해야 했다. HLD구현을 보다가, HLD의 각 그룹마다 세그먼트 트리를 만드는 대신 세그먼트 트리 하나로 전체 HLD쿼리를 수행할 수 있음을 깨달았다.

트리를 순회하면서, heavy에 해당하는 자식 노드를 먼저 방문하면서 번호를 매긴다(hld를 구성할 때 이미 heavy를 먼저 방문하게 구현되어 있었다). 두 정점 u, v에 대한 쿼리는 아래와 같이 처리한다.

• u, v가 같은 그룹: u의 발견 번호부터 v의 발견 번호까지 구간 질의 실행
• u, v가 다른 그룹: v가 속한 그룹의 해드 노드 h의 발견 번호부터 v의 발견 번호까지 구간 질의 실행, u와 h의 부모에 대한 질의로 재귀.

곱셈과 덧셈을 번갈아 처리하는 방법은 아래 문제를 풀 때와 같이 해결한다.

https://www.acmicpc.net/problem/13925

13925번: 수열과 쿼리 13