jhljx又来了(I)

题目描述

听说大家开始学习数据结构。那么必然要接触到树这种东西。于是jhljx就在南湖旁边精心种植了一棵二叉树。 长这样。。

这是一个标准的二叉树，每个结点有一个编号n，n按照从小到大的顺序依次编号。 那么问题来了，给你两个结点的编号x和y，请你求出他们的最近公共祖先的编号。

But what is “最近公共祖先”？ 说白了就是离这两个结点最近的祖先结点。 比如说结点8和结点5，他们的最近公共祖先是2，结点8和结点9的最近公共祖先则是4。

输入

输入多组数据。 每组数据为两个数x和y(1<=x,y<=2^32)。

输出

输出这两个结点的最近公共祖先的序号。

输入样例

2 6
6 7
3 5
8 9
8 11

输出样例

1
3
1
4
2

Hint

本题只是以数据结构为背景，考察的仍是C语言基础知识（以及数学）。 最近公共祖先：Least Common Ancestors

Powered by jhljx, given by AZY.