最终会走到的层是一段区间 $[l,r]$，可以考虑双指针。设 $d_u$ 为 $u$ 所在的层，对连边做以下修改：

• 不妨设 $d_A\leq d_B$，将所有 $[d_A,d_B]$ 层之间的内部连边全部合并，用并查集缩点。
• 对于 $x\leq d_A-1$ 考虑 $x,x+1$ 层之间的连边，由于 $x$ 被加入时必然有 $x+1$ 被加入，因此对于 $x$ 会被合并成的等价类，直接缩成一个点显然不影响。对于 $x$ 从大到小递推，形成的是一个树的结构。对于 $x\ge d_B+1$ 同理做即可。

这样形成两棵分别向左和向右的树 $T_1,T_2$。从小到大枚举 $r$，显然 $T_1,T_2$ 的所有叶子就是 $[d_A,d_B]$ 层内部加边时形成的连通块。发现 $r$ 的作用就是在叶子之间连边，如果没有叶子的操作，那么 $l$ 取的就是 $\text{LCA}(A,B)$ 所在的深度。考虑合并叶子，事实上就是取出 $x\to \text{LCA},y\to \text{LCA}$ 的路径，对于相同深度的点做合并。

对于合并事件，每次有效的合并是深度从大到小的一段前缀，并且总量线性，因此可以暴力。取出 $A\to \text{LCA}(A,B),B\to \text{LCA}(A,B)$ 的路径 $p,q$，答案即为极长后缀使得 $p_i,q_i$ 等价，可以双指针线性做。

时间复杂度 $O(n\alpha(n))$。