트리 최소 공통 조상 알고리즘
\(\texttt{0x00}\) 개념
루트 트리에서 노드 \(z\)가 노드 \(x\)와 \(y\)의 공통 조상일 때, \(x\)와 \(y\)의 모든 공통 조상 중 깊이가 최대인 노드를 **최소 공통 조상(LCA)**이라 하며 \(\text{LCA}(x,y)\)로 표기합니다.
\(\texttt{0x01}\) 계산 방법
1. 트리 이진 증가
접근법:
상향 표식법을 개선한 방법으로, 매 단계마다 \(2^k\) 레벨 상위 조상으로 이동합니다. \ ...
7월 17일 23:31에 게시됨