[백준] 23355. 공사

newbieski·2021년 11월 12일
0

백준

목록 보기
41/210

https://www.acmicpc.net/problem/23355

요약

  • 트리가 주어지고, 쿼리를 수행함
  • x ~ y 경로에 점 u가 있는지
  • x ~ y 경로에 u-v로 된 간선이 있는지

접근법

  • HLD로 접근함
  • HLD의 subtree는 오일러투어 번호가 연속적임을 이용해서
  • 연속 구간 안에 점 u가 있는지를 판단해나갈 수 있음
  • 간선은 두 점 모두가 있는지를 판단하면 됨

다른 접근법

  • 문제 알고리즘이 LCA로 되어있고, HLD로 보기에는 티어가 너무 낮아서 다른 사람 코드를 찾아봄
  • LCA를 이용하는 방법인데 나는 더 진행을 못한 아이디어임
  • x ~ y경로는 LCA를 반드시 지남
  • 점 u는 LCA 하위에 있어야함(subtree에 속해야함)
  • 점 u의 subtree안에 x가 있거나, 점 u의 subtree안에 y가 있으면 u는 경로에 있다고 볼 수 있음 ==> 내가 생각 못한 아이디어
profile
newbieski

0개의 댓글