트리의 두 정점 u, v에 대해 최소 공통 조상(Lowest Common Ancestor, LCA)은 두 정점의 조상이면서 가장 깊은 정점입니다. 매 질의마다 부모 포인터를 한 단계씩 따라가면 깊이 차이가 큰 경우 오래 걸립니다. Binary lifting은 v에서 2^k단계 위의 조상을 up[v][k]에 저장하고, 질의에서 깊이 차이를 이진수의 켜진 비트로 분해해 여러 단계를 한 번에 점프합니다. 두 정점을 같은 깊이로 맞춘 뒤, 높은 점프부터 두 조상이 달라지는 동안 함께 올리면 LCA 직전까지 이동할 수 있습니다.
이 방법은 먼저 하나의 root를 고정한 rooted tree 모델에 의존합니다. 같은 무방향 트리라도 root가 달라지면 각 정점의 조상·깊이·LCA가 달라지므로 root를 질의 입력처럼 매번 바꾸는 문제와 고정 root에서의 LCA를 구하는 문제를 분리해야 합니다.
루트 트리와 조상 표
루트를 1로 둔 트리에 다음 간선을 두겠습니다: 1-2, 1-3, 2-4, 2-5, 3-6, 5-7. 깊이는 depth[1]=0, depth[2]=depth[3]=1, depth[4]=depth[5]=depth[6]=2, depth[7]=3입니다. 부모 배열은 parent[1]=1, parent[2]=1, parent[3]=1, parent[4]=2, parent[5]=2, parent[6]=3, parent[7]=5처럼 root가 자기 자신을 부모로 가리키게 하겠습니다.
up[v][0]은 1단계 부모입니다. up[v][k]는 up[ up[v][k-1] ][k-1]로 만듭니다. 예를 들어 up[7][0]=5, up[7][1]=2, up[7][2]=1, up[7][3]=1입니다. root의 parent를 자기 자신으로 두면 root 위로 점프해도 sentinel을 실제 정점으로 오인하지 않고 1에 머뭅니다. null을 사용할 수도 있지만 모든 표 조회에 경계 검사를 추가해야 합니다.
그림을 글로 읽기
- 정점 7: depth = 3 · parent = 5
- up[7][0] = 5: 1단계 위 · 2^0
- up[7][1] = 2: 2단계 위 · 2^1
- up[7][2] = 1: 4단계 위 · root에서 고정
- 정점 7 → up[7][0] = 5: 한 번 점프
- 정점 7 → up[7][1] = 2: 두 번 점프
- up[7][1] = 2 → up[7][2] = 1: 표의 재귀 구성
DFS 전처리에서 각 정점을 방문할 때 up[v][0]과 높은 레벨을 채우고, tin[v]를 입장 시각에, tout[v]를 모든 자손 처리가 끝난 뒤 기록합니다. LOG는 2^LOG가 최대 깊이를 덮도록 잡습니다. 저장소와 언어가 재귀 깊이 제한을 어떻게 처리하는지는 별도 구현 문제이므로, 깊은 트리에서는 명시적 stack으로 DFS 사건을 저장할지 확인해야 합니다.
tin·tout와 조상 판정
DFS의 시간 구간에서 u가 v의 조상이면 tin[u] ≤ tin[v]이고 tout[v] ≤ tout[u]입니다. 이를 is_ancestor(u,v)로 묶으면 질의 시작 시 endpoint가 답인 경우를 빠르게 처리할 수 있습니다. u=v도 자기 자신의 조상으로 정의하면 동일 정점 질의는 바로 u를 반환합니다.
discovery 순서 tin만 비교하면 충분하지 않습니다. 형제 subtree에서 나중에 발견된 정점도 tin이 더 크기 때문에, tin[u] ≤ tin[v]만으로는 u가 조상이라고 오인합니다. tout가 u의 subtree를 벗어난 시점을 나타내므로 두 조건을 함께 써야 합니다. 시간 증가 카운터를 입장·퇴장 모두에서 올리는지, 구간을 반열린 형태로 기록하는지는 구현에서 일관되어야 하지만 containment 식은 같은 의미를 유지해야 합니다.
깊이 맞춤과 이진 점프
LCA(7,4)를 계산하겠습니다. 깊이는 3과 2이므로 먼저 7을 한 단계 올립니다. 깊이 차이 d=1은 이진 001이고 up[7][0]=5라서 u=5가 됩니다. 이제 두 정점은 모두 깊이 2입니다. u=5, v=4는 부모가 모두 2이므로 2가 LCA입니다.
d=13을 예로 들면 13=8+4+1입니다. 어떤 정점 v에서 13단계 위 조상을 구할 때, 현재 정점에 up[cur][3], 다음 cur에 up[cur][2], 마지막에 up[cur][0]을 적용합니다. 순서를 낮은 비트부터 적용해도 각 단계의 “현재 위치에서 2^k”를 정확히 사용하면 합계는 같지만, root를 넘어가는 정책과 구현의 bit loop 방향을 함께 확인해야 합니다. 실제 트리 높이가 13보다 작으면 root 자기참조 또는 sentinel 정책이 결과를 결정합니다.
두 정점의 깊이를 맞춘 뒤에는 k=LOG-1부터 0까지 검사합니다. up[u][k] != up[v][k]이면 두 정점을 각각 그 조상으로 올립니다. 같은 조상으로 점프하는 순간은 LCA를 넘어설 수 있으므로 건너뛰고, 마지막에 parent[u]를 반환합니다. endpoint ancestor 검사를 먼저 하지 않으면 u가 v의 조상인 경우 u 자체를 보존하지 못하거나 root 위 경계에서 잘못된 값을 반환할 수 있습니다.
query trace와 표의 중간 상태
LCA(7,6)을 추적해 보겠습니다. 7의 깊이는 3, 6은 2이므로 7을 up[7][0]=5로 올립니다. 이제 (u,v)=(5,6)이고 둘 다 깊이 2입니다. k=2에서 up[5][2]=1, up[6][2]=1로 같으므로 점프하지 않습니다. k=1에서는 up[5][1]=1, up[6][1]=1로 역시 같습니다. k=0에서는 up[5][0]=2, up[6][0]=3으로 다르므로 각각 2와 3으로 올립니다. 마지막 parent[2]=1을 반환합니다.
이 trace는 “가장 높은 점프부터”가 단지 최적화가 아니라, LCA보다 위로 올라가지 않는 최대 전진을 먼저 선택하는 절차임을 보여 줍니다. 낮은 점프만 반복해도 정답은 구할 수 있지만 한 질의가 O(depth)가 되고, 높은 점프부터 검사하면 표 조회 O(1)을 LOG번 수행합니다. up 표가 parent 정의와 다른 세대의 tree에서 만들어졌다면 숫자 배열이 그럴듯해도 query의 의미는 깨집니다.
전처리와 질의 비용
정점 수를 N, LOG=ceil(log2 N) 수준으로 두면 DFS에서 각 정점의 up 열을 채우는 비용은 O(N log N), 조상 query는 O(log N)입니다. up 표가 N×LOG이므로 공간도 O(N log N)입니다. tin, tout, depth, parent 배열은 별도의 O(N) 공간입니다. 무방향 입력은 parent edge를 다시 따라가지 않도록 edge identity 또는 parent 정점 조건을 사용하고, disconnected 입력이라면 root에서 모든 정점이 도달하는지 검증해야 합니다.
질의가 매우 많고 트리가 고정이면 이 전처리 비용을 여러 query가 나눠 부담합니다. 반대로 트리가 자주 바뀌면 up 표를 갱신하는 비용이 질의 이득보다 커질 수 있어 Euler tour + RMQ, Link-Cut Tree 등 다른 구조를 검토할 수 있지만, 각각의 업데이트·질의 계약이 다릅니다. Binary lifting은 정적 또는 변경이 드문 rooted tree에서 단순한 메모리-시간 절충으로 이해하는 것이 정확합니다.
root 변경과 세 번의 LCA
고정 root R0로 만든 LCA 전처리를 재사용하면서 질의마다 새로운 root r에서의 LCA_r(u,v)를 구할 수 있습니다. 세 후보 a=lca_0(u,v), b=lca_0(u,r), c=lca_0(v,r)를 계산하고, 원래 고정 root에서 depth가 가장 깊은 후보를 선택하면 됩니다. 이 규칙은 새 root로 매번 ancestor table을 재구축하지 않는 방법입니다.
예를 들어 고정 root가 1이고 간선이 앞의 트리일 때 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으로 재배치하면 3에서 2를 거쳐 4와 7로 내려가는 두 경로의 공통 분기점이 2입니다.
다른 모양에서는 세 후보가 서로 달라질 수 있지만 가장 깊은 고정-root 후보 규칙은 같은 트리의 경로 교차를 표현합니다. 이 방법을 쓸 때 depth를 새 root 기준으로 다시 계산하면 안 됩니다. 표와 depth는 모두 R0 기준으로 남겨야 하며, r은 세 query의 한 입력일 뿐입니다. root가 바뀌었다고 tin/tout을 새 의미로 해석하면 식의 전제가 깨집니다.
실패 조건과 검증
검증은 단일 노드, root query, 한쪽으로 긴 트리, 형제 subtree, u=v, u가 v의 조상인 경우를 포함해야 합니다. 무작위 작은 트리에서는 두 정점의 부모를 직접 따라 올려 얻은 결과와 binary lifting 결과를 비교합니다. root 변경 query는 새 root로 실제 parent를 다시 만든 느린 기준 구현과 세 번의 고정-root LCA 결과를 대조할 수 있습니다.
흔한 버그는 LOG가 부족해 가장 높은 bit를 버리는 것, root parent를 null로 두고 null table을 조회하는 것, tin만으로 ancestor를 판단하는 것, endpoint 검사 전에 두 정점을 동시에 올리는 것입니다. 재귀 DFS가 깊은 사슬에서 호출 스택을 넘는지, 시간 카운터가 integer 범위를 넘는지도 구현 언어의 실행 환경에서 별도로 확인해야 합니다.
참고 자료와 검증 범위
- Lowest Common Ancestor - Binary Lifting — cp-algorithms, 2026-08-07 갱신본의 본문을 2026-09-19 확인했습니다.
O(N log N)전처리, entry/exit time 조상 판정,O(log N)query의 근거로 사용했습니다. - 트리 구조와 순회 알고리즘 — 저장소 노트의 root/depth/parent 어휘와 DFS 사건을 대조했습니다.
- root 변경의 세 LCA 공식은 이 문서의 입력 모델과 고정-root 경로 관계에서 설명한 corrected mechanism입니다. 예제 값은 손으로 계산했으며 실행 측정 결과가 아닙니다.