二叉树（暑假每日一题 31）

     1
    / \
   2   3
  / \ / \
 4  5 6  7
/\ /\ /\ /\
...     ... 
1
2
3
4
5
6
7

如上图所示，由正整数 $1,2,3,\dots$ 组成了一棵无限大的（满）二叉树。

从任意一个结点到根结点（编号是 $1$ 的结点）都有一条唯一的路径，比如从 $5$ 到根结点的路径是 $(5,2,1)$，从 $4$ 到根结点的路径是 $(4,2,1)$，从根结点 $1$ 到根结点的路径上只包含一个结点 1，因此路径就是 $(1)$。

对于两个结点 x 和 y，假设他们到根结点的路径分别是 $(x_1,x_2,\dots ,1)$ 和 $(y_1,y_2,\dots ,1)$，那么必然存在两个正整数 $i$ 和 $j$，使得从 $x_i$ 和 $y_j$ 开始，有 $x_i=y_j,x_{i+1}=y_{j+1},x_{i+2}=y_{j+2},\dots$
现在的问题就是，给定 $x$ 和 $y$，要求他们的公共父节点，即 $x_i$（也就是 $y_j$）。

输入格式
$1\le x,y\le 2^{31}-1$
输入样例：

10 4
1

输出样例：

2
1

---

#include

using namespace std;

int main(){
    
    int x, y;
    cin >> x >> y;
    while(x != y){
        if(x > y) x >>= 1;
        else y >>= 1;
    }
    
    cout << x << endl;
    
    return 0;
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17