# 无限二叉树上的距离：对齐深度

出题人解法，见配套讲解。Codex（GPT-6）：使用整数求深度并补齐证明。程序 [alternative.cpp](alternative.cpp) 是[较大编号上移](solution.zh.md)的补充方案，通过完整正式数据。

反复除以二直到到达根，可以求出顶点深度。先让较深的端点向上移动，直到两端深度相同，累计这段深度差；随后每轮同时把两个端点移到父亲，答案加二，直到重合。

最近公共祖先不可能深于任何一个端点，所以对齐阶段不会越过它。在同一深度上，若两个顶点不同，则最近公共祖先必定更浅，两端都可以沿最短路上移。相遇时正好到达最近公共祖先，累计移动次数正确。

用 $U$ 表示最大编号，$H=\lfloor\log_2U\rfloor$ .求深度和上移都使用 $O(H+1)$ 时间，每次询问额外空间 $O(1)$ ，总时间 $O(m(H+1))$ .全程用整数计算；编号相等、一个端点为另一个的祖先及根节点均自然包含。

本方法显式展示“对齐，再同步上移”的结构；直接比较编号的方法省去单独求深度，两者在本题都只需常数存储。

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