LCA query에서 한 정점이 다른 정점의 조상인지 먼저 tin/tout으로 검사하는 이유는 무엇인가요?

tin[u] ≤ tin[v]이면서 tout[v] ≤ tout[u]이면 DFS에서 v의 전체 subtree가 u의 방문 구간 안에 있으므로 u가 v의 조상입니다. 이 검사는 O(1)에 가능하고, u가 v의 조상인 경우 답 자체가 u이므로 두 정점을 동시에 위로 올리는 일반 루프를 실행하지 않아도 됩니다. 반대로 v가 u의 조상이면 v를 바로 반환합니다.

예를 들어 u의 subtree를 DFS 구간 [2,9], v를 [5,6]으로 기록했다면 v의 입장·퇴장이 u의 구간 안에 있어 u가 v의 조상입니다. discovery 시간만 비교하면 u보다 늦게 방문된 형제 subtree 정점도 조상으로 오인할 수 있습니다. tout은 해당 subtree의 모든 자손 처리가 끝난 시점을 보여 주므로 containment의 두 번째 조건입니다.

endpoint 검사를 생략하면 u가 v의 조상일 때 jump loop가 u를 지나 더 위 조상으로 올릴 수 있습니다. 자기 자신 query도 자기 조상으로 처리하면 즉시 반환됩니다. 다만 tin/tout의 카운터 증가 방식은 구현마다 다를 수 있으므로, 입장·퇴장 사건의 순서와 is_ancestor 비교자가 같은 정의를 사용해야 합니다.

분기 트리에서 형제 정점을 반례로 볼 수 있습니다. u의 interval이 [2,9]이고 형제 subtree의 w가 [10,13]이면 tin[u]=2 < tin[w]=10이지만 tout[w]=13 ≤ tout[u]=9가 아니므로 u는 w의 조상이 아닙니다. 이 검사는 LCA 루프의 endpoint 보존뿐 아니라 subtree 범위 질의의 경계에도 쓰입니다. 단, disconnected 입력에서 서로 다른 DFS component의 시간을 한 카운터로 합치면 숫자 containment만으로 조상이라고 오인할 수 있으므로 component/root ID도 함께 확인해야 합니다.