本题就相当于找 lca。

方法一：像树剖找 lca 一样，让深度最大的点（其实就是值更大的点）往上跳一步（u = u / 2），最后跳到 lca 的位置时跳的步数就是两点之间的边数。

while(n != m) {
	if(n < m) swap(n, m);
	n /= 2, ans++;
}
return printf("%lld\n", ans);

方法二：先假定 lca $=1$，然后每次判断两个点是不是在 lca 的同一侧，如果否那么现在的lca就是真正的 lca；否则我们把 lca 设为两个点那一侧的儿子，同时答案 $-2$，然后继续计算，直到两个点不同侧或一个点成为 lca。

代码又臭又长，就不贴了。

注意判断两个点是否在同一侧时令 fn = n * 2 - ln + 1（ln 为 lca 的子树内 n 所在层的节点个数，即如果 n 超过了其一半说明 n 在右侧；m同理），如果fn * fm < 0说明两个点不在同一侧。注意如果直接乘可能会爆 long long，我们应该先把fn换成sgn(fn)； 记得特判 lca = n 的情况。

说句闲话，这题解怎么还可以自己赞/踩自己呢

这题有点毒。 接下来我将以我的角度分享这题思路。

开题： 树上最短路？ 裸LCA，离线？直接tarjan！ 一看数据$2^{18}$，6。

10min后 考虑数学方法，是否有公式？ 啊啊啊啊啊啊啊啊啊……；

20min后 考虑删掉无关子树，就变成了很深的一棵树，其实也就logn。 让后跑LCA。

最后： 人生苦短，我打暴力。