문제

• 
• 시간 제한: 1초
• 메모리 제한: 256MB

Problem Analysis

먼저, 문제 상황은 트리의 특성을 갖고 있다. 따라서, 두 도시를 잇는 경로를 찾기 위해선, LCA를 찾으면 된다. 이후에, naive 하게, 경로를 직접 따라가면서 최대와 최소를 구하는 방법은 최악의 경우 시간 복잡도가 O(N)이다. 대신에, 각 node마다, ancestors까지의 최대 최소를 미리 저장하고 있다면, 시간을 대폭 줄일 수 있을 것이다.

Algorithm

Binary Lifting를 하기 위한 dp에 ancestor와, 해당 ancestor까지의 최대 최소도 추가로 함께 저장한다.
이후, Binary lifting을 하여 lca를 찾음과 동시에 max와 min도 함께 찾아 출력한다.

Data Structure

• dp[i][j]: 각 dp에 i-th node의 (2^j)-th ancestor를 저장하고, 동시에 해당 경로상의 최대와 최소를 저장한다.

결과

Other

시간 복잡도는 dp 생성에 O(NlogN), 각 쿼리에 O(logN)이다.