# 无限二叉树上的距离：较大编号向上走

出题人解法：每次将较大编号移动到父亲；配套讲解也给出了按深度对齐的方法。Codex（GPT-6）：整理整数实现、证明及大编号边界。

## 算法

非根顶点 $v$ 的父亲是 $\lfloor v/2\rfloor$ .当 $a\ne b$ 时，选编号较大的端点，将其除以二下取整，并把答案加一。两端相等时结束。

## 为什么不会越过汇合点

这张图是一棵以 $1$ 为根的树：每个其他顶点恰有一个更小的父亲，反复取父亲最终到达根。任意两点之间只有一条简单路径，它经过两者的最近公共祖先。

若当前 $a>b$ ，则 $a$ 不可能是 $b$ 的祖先，因为真祖先的编号严格更小。因此 $a$ 尚未到达两端的最近公共祖先，把它移到父亲正好沿最短路走一步，不会跨过该祖先。每次操作都使剩余距离减少一；两端最终在最近公共祖先处相遇，累计次数就是最短距离。

## 复杂度与数值

令 $U$ 为询问中最大的顶点编号，$H=\lfloor\log_2U\rfloor$ 为最大深度。每次询问最多移动 $2H$ 步，总时间 $O(m(H+1))$ ，额外空间 $O(1)$ .

本题 $U\le10^{18}$ ，深度至多 $59$ ，距离至多 $118$ .编号使用至少 64 位的无符号整数，距离用普通整数即可；不需要建立无限树，也不需要浮点对数。相同端点直接输出零。

[std.cpp](std.cpp) 保留较大编号上移的首选方案。[按深度对齐](solution-alternative.zh.md)及 [alternative.cpp](alternative.cpp)显式计算深度，便于理解一般树的公共祖先过程，但复杂度相同。两种方法均通过完整正式数据。

测试配方见 [plan.json](tests/plan.json)，生成方式见[数据生成说明](../../../README.md#使用题目文件)。参考环境、逐次测量和适用范围见[评测说明](../../../docs/评测环境与性能.md)。