같은 트리의 LCA 질의마다 root가 바뀝니다. 고정 root 전처리 세 번의 LCA로 새 답을 구할 수 있나요?

구두 답변

정의를 외우기보다, 원리와 조건을 연결해 설명해 보세요.

가능합니다. 고정 root R0에서 전처리한 LCA를 사용해 a=lca_0(u,v), b=lca_0(u,r), c=lca_0(v,r)를 구한 뒤, 고정 root 기준 depth가 가장 깊은 후보를 반환하면 root=r에서의 LCA가 됩니다. 매 query마다 root를 바꾸어 up 표와 tin/tout을 재구축할 필요가 없습니다.

구체적으로 고정 root가 1이고 간선이 1-2, 1-3, 2-4, 2-5, 3-6, 5-7인 트리를 보겠습니다. u=4, v=7, 새 root r=3이면 lca_0(4,7)=2, lca_0(4,3)=1, lca_0(7,3)=1입니다. 고정 root depth는 각각 2, 0, 0이므로 답은 2입니다. 실제로 root를 3으로 바라보아도 4와 7의 경로가 공유하는 가장 깊은 가지는 2입니다.

이 공식에서 depth와 LCA 표는 끝까지 R0 기준이어야 합니다. r만 입력으로 넣고 기존 tin/tout을 새 root의 ancestor 판정처럼 읽으면 전제가 깨집니다. 또한 이는 같은 정적 무방향 트리에서 root 관점만 바꾸는 경우입니다. 간선 삽입·삭제가 있거나 root 변경 자체가 구조 업데이트라면 표의 유효 세대와 재전처리 정책을 별도로 관리해야 합니다.

세 후보 공식의 이유는 u와 v를 잇는 단순 경로와 질의 root r의 위치에 있습니다. 고정 root 기준 a=lca0(u,v)는 원래 경로의 분기점이고, b, c는 r이 그 경로의 어느 쪽에 놓였는지를 나타냅니다. 가장 깊은 후보가 새 root에서 두 정점의 경로가 만나는 지점이 됩니다. 앞서의 분기 트리에서 u=4,v=7,r=3이면 후보가 2,1,1이므로 2를 반환합니다. 간선이 바뀌면 고정 표가 표현하는 경로 자체가 바뀌므로 세 번 호출만으로는 갱신을 대체할 수 없습니다.

득점 포인트

이해가 드러나는 지점을 확인해 보세요.

세 후보 lca(u,v), lca(u,r), lca(v,r)를 정확히 만들고 deepest original depth를 선택한다.
1-2, 1-3, 2-4, 2-5, 3-6, 5-7인 분기 트리에서 후보값과 답 2를 추적한다.
고정 root 기준 depth/tin/tout을 재사용하되 새 root로 재해석하지 않는다고 말한다.

감점 포인트

놓치기 쉬운 조건과 오해를 짚어 보세요.

세 후보 중 아무 후보나 반환하거나 depth를 새 root 기준으로 다시 계산한다.
root가 바뀌었으니 기존 up 표를 바로 새 ancestor table이라고 주장한다.
트리 구조가 변경되어도 세 번의 query만 하면 표가 계속 유효하다고 말한다.

더 파고들 거리

하나 더 질문하며 이해의 범위를 넓혀 보세요.

세 후보의 depth가 동률일 때 실제로 같은 정점이 되는 이유와 tie 처리 코드를 어떻게 작성할지 설명해 보세요.
root query가 매우 잦고 간선 변경도 있다면 binary lifting과 동적 트리 자료구조의 비용 경계를 어떻게 판단하나요?

득점·감점 포인트는 학습용 자기 점검 기준이며, 특정 회사의 실제 채점표가 아닙니다.