어떠한 무한히 이어지는 완벽한 이분 트리가 주어진다. 트리의 각 정점은 1번부터 계속 번호가 매겨져 있으며, 루트는 1번이다.
1
2 / 3
4 , 5 / 6 , 7
8 , 9 / 10, 11/ 12, 13/ 14 , 15
.
.
.
두 노드의 쌍 (a,b)(1 ≤ (a,b) ≤ 10,000)개가 주어졌을 때, 두 노드의 가장 가까운 공통 조상 을 f(a,b)로 정의 한다.(예를 들어 5와 8의 공통조상(LCA)는 2이다.)
(1) f(4096,4095)를 구하시오
(2) f(a,b)=1이 되는 a,b를 구하시오
(3) f(a,b)를 a,b에 대한 식으로 일반화 하시오
좋아요
0
글쎄요
0
어려워요
0