P11364 [NOIP2024] 树上查询

死于交集关系推导。

首先，区间 $\text{LCA}$ 的深度为：

可以用虚树的方法证。

我们找出以 $\text{LCA}(i,i+1)$ 为最近公共祖先的最大区间 $[x_i,y_i,v_i]$，$v_i$ 为 $\text{dep}_{\text{LCA}(i,i+1)}$。

显然，查询是求与 $[l,r]$ 交集至少为 $k$，且最大的 $v_i$。可列出两个不等式。

第一个对 $r$ 扫描线，第二个对 $k$ 扫描线，时间复杂度 $O(n\log n)$。