joseph0528 코딩 블로그

문제에 쓰여있는 그대로 R를 루트노드라고 하고 LCA(U, V)를 구해주면 끝인 문제이다. 이 문제를 처음 봤을 때 LCA의 sparse table를 입력마다 갱신하는 방법이 바로 떠오르겠지만 그럴 경우 코드를 작성하지 않아도 안된다는 것을 알 수 있다. 그럼 어떻게 해야 할까 이 그림은 위 문제의 테스트케이스를 그래프로 나타낸 것이다. 이때 (U, V)에 대해 R의 위치는 1. R 이 LCA(U, V) 보다 위에 있을 때, 2. R 이 V -> LCA(U, V) 사이에 있는 노드와 연결되어 있을 때, 3. R 이 U -> LCA(U,V) 사이에 있는 노드와 연결되어있을 때, 4. R이 루트 노드를 거쳐 U, V를 가야 할 때 이렇게 총 4개가 나오게 된다. 그럼 처음부터 따져보자. 위 그림은 1번 경우..