3176. 도로 네트워크

800문제 달성 기념.

---

N개의 도시와 N-1개의 도로가 있다. 여기에서 도로망이 트리 형태임을 알 수 있다.

 

어떤 도시 A와 B를 연결하는 최단 경로는 A~LCA~B이다. 정답을 구하기 위해서는 이 경로에 속한 도로의 길이의 최댓값과 최솟값을 찾으면 된다.

 

LCA를 O(logN)에 찾는 방법은 널리 알려져 있다. 따라서 우리가 할 일은 도로를 탐색하는 것이다. 그런데 도로가 최대 99999개네? 도로를 전부 탐색하면 O(N^2)이 되기 때문에 시간 제한에 걸릴 것 같다. 쿼리 1개당 O(logN) 안에 처리해야 할 것 같다.

 

답은 이미 나와 있다. LCA를 O(logN)에 구한 것처럼 도로도 O(logN)에 탐색하면 된다. LCA를 탐색할 때 "이 정점의 2^i번째 부모"를 찾은 것처럼, "이 정점부터 2^i번째 부모까지의 도로를 탐색한 결과"를 저장하면 된다. 그 후엔 LCA를 찾듯이 정답을 찾으면 된다.

 

낫 놓고 기역자도 모를 뻔 했다..ㅋㅋ

---

여담.

디버깅하다가 cout.flush()를 썼는데, 제출할 때 이걸 지우지 않아서 계속 시간초과가 났다. 10분동안 고민하다가 겨우 찾았다..