먼저, 문제 상황은 트리의 특성을 갖고 있다. 따라서, 두 도시를 잇는 경로를 찾기 위해선, LCA를 찾으면 된다. 이후에, naive 하게, 경로를 직접 따라가면서 최대와 최소를 구하는 방법은 최악의 경우 시간 복잡도가 O(N)이다. 대신에, 각 node마다, ancestors까지의 최대 최소를 미리 저장하고 있다면, 시간을 대폭 줄일 수 있을 것이다.
Binary Lifting를 하기 위한 dp에 ancestor와, 해당 ancestor까지의 최대 최소도 추가로 함께 저장한다.
이후, Binary lifting을 하여 lca를 찾음과 동시에 max와 min도 함께 찾아 출력한다.
시간 복잡도는 dp 생성에 O(NlogN), 각 쿼리에 O(logN)이다.