树上查询

设 $a_i=\mathrm{dep}_{\mathrm{LCA}^{*}(i,i+1)}$。对于 $l<r$，可以发现

我们令 $r \gets r-1,k \gets k-1$。

于是问题变为求与询问区间 $[l,r]$ 中长度至少为 $k$ 的区间中 $\min$ 的 $\max$。

从大到小加入 $a_i$，维护 $\mathcal{O}(n)$ 个极长连续段 $(x_j,y_j,v_j)$ 表示 $x_j \le i \le y_j$ 均有 $a_i \ge v_j$。每次询问考虑 $[l,r]$ 和 $[x_j,y_j]$ 的交集大小 $\ge k$ 即可。

对于“交集大小至少为 $k$”，我们可以写出两个不等式，满足其一即可：

两个都可以在 $\mathcal{O}(n \log n)$ 的时间复杂度内求解。