对于询问 $(l,r,u)$，令 $b_i$ 表示保留 $a_{l\sim r}$ 后 $i$ 子树内的点数，设 $j$ 是 $i$ 在 $u$ 方向上的儿子，则 $i$ 是合法 LCA 当且仅当 $b_i>b_j$。

树剖。当 $j$ 是轻儿子时可以用数据结构求出 $b$ 暴力比较，这部分时间复杂度 $O(q\log^2 n)$。$j$ 是重儿子时，维护是否有 $b_i>b_j$，容易发现点亮一个 $a_k$ 会将 $a_k$ 往上每条重链遇到的第一个点标记为合法。对于每条重链分别处理，这样会有 $O(m\log n)$ 次将一个点标记为合法，$O(q\log n)$ 次查询这条重链上前缀编号最大的合法点，额外的限制 $(l,r)$ 可以用线段树直接维护。总时间复杂度 $2\log$，稍微卡一下常就过了。