root가 계속 변하는 게 핵심이다. RMQ를 위해 pre-processing을 하는 데 O(N)의 시간 복잡도를 갖기에, 매번 새로 생성하는 건 불가능하다. 하지만, 조금 더 분석을 해보면, 아래와 같이 처음에 root를 1로 잡고 (4, 6)의 lca를 찾는 상황에서, 빨간색으로 root가 변할 때만 lca가 달라진다. 빨간색과 파란색을 구분할 수 있다면 풀이에 도움이 될 것 같다.
파란색 선과 다르게 빨간색 선에서 새로운 root r을 선택하면, r에서 u와 v로 갈 때, 한 가지 경로는 기존 lca를 거치지만, 다른 경로는 lca를 거치지 않는다. 따라서, lca( r, u )와 lca( r, v )가 파란색이면 같고 빨간색이면 다르다. 이를 이용하면, 정답을 쉽게 구할 수 있다.
시간 복잡도는 segTree 생성에 O(N), 각 쿼리마다 O(logN)이다.
이처럼 Naive 한 풀이에서 문제가 되는 부분을 찾고, 해당 부분을 해결하기 위해, 이용할 만한 새로운 특징이나 관점을 찾아내는 게, PS에서 굉장히 중요한 것 같다.