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는 경로에 있다고 볼 수 있음 ==> 내가 생각 못한 아이디어