给你一颗树，有 $q$ 个询问，每次给你一个区间和一个要求的长度，询问最深的区间 $\operatorname{lca}$ 的深度。

看到题目后大概能猜测出是一道数据结构题，当下的数据结构题目往往是需要找到性质才能更好地维护。

学过虚树的二次排序建树后可以迅速看出区间的 $\operatorname{lca}$ 的深度转化为了 $\min_{i=l}^{r-1}{\mathit{dep}_{\operatorname{lca}(i,i+1)}}$。如果不知道虚树也可以手玩样例或讨论特殊情况来寻找性质。

在找到性质后，我们便自然地存下 $\operatorname{lca}(i,i+1)$。然后我们最后要求的答案就变成了 $\max \min \mathit{dep}_{\operatorname{lca}(i,i+1)}$。那么便考虑对于一个 $\operatorname{lca}(i,i+1)$ 来说，它什么时候会变为某个区间的答案。

于是我们便可以对每一个 $\operatorname{lca}(i,i+1)$ 求出它会成为的的最长区间 $[L,R]$，单调栈就可以解决。

那么如果该 $\operatorname{lca}(i,i+1)$ 能对一个询问产生贡献，说明两个区间有交，可以写出式子：