15480. LCA와 쿼리

smsh0722·2022년 4월 12일
0

Tree

목록 보기
3/5

문제

  • 시간 제한: 2초
  • 메모리 제한: 512MB

Problem Analysis

root가 계속 변하는 게 핵심이다. RMQ를 위해 pre-processing을 하는 데 O(N)의 시간 복잡도를 갖기에, 매번 새로 생성하는 건 불가능하다. 하지만, 조금 더 분석을 해보면, 아래와 같이 처음에 root를 1로 잡고 (4, 6)의 lca를 찾는 상황에서, 빨간색으로 root가 변할 때만 lca가 달라진다. 빨간색과 파란색을 구분할 수 있다면 풀이에 도움이 될 것 같다.

Algorithm

파란색 선과 다르게 빨간색 선에서 새로운 root r을 선택하면, r에서 u와 v로 갈 때, 한 가지 경로는 기존 lca를 거치지만, 다른 경로는 lca를 거치지 않는다. 따라서, lca( r, u )와 lca( r, v )가 파란색이면 같고 빨간색이면 다르다. 이를 이용하면, 정답을 쉽게 구할 수 있다.

  • 파란색: lca( u, v )가 최종 lca다
  • 빨간색: lca( r, u )와 lca( r, v ) 중에서 lca( u, v )와 같지 않은 것이 최종 lca다

Data Structure

  • Segment Tree[]: RMQ용
  • adjList[]: adjacency list

결과

Other

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

이처럼 Naive 한 풀이에서 문제가 되는 부분을 찾고, 해당 부분을 해결하기 위해, 이용할 만한 새로운 특징이나 관점을 찾아내는 게, PS에서 굉장히 중요한 것 같다.

profile
Military service - May 31, 2022 ~ Nov. 30, 2023

0개의 댓글