题解：P11364 [NOIP2024] 树上查询

thomaswmy · 2024-11-30 17:01:22 · 题解

首先按照线段树结构分治。那么只要算跨过中点的答案。

注意到跨过中点的区间 LCA 一定是 \texttt{LCA}(mid,mid+1) 的祖先，可以先求出 \texttt{LCA}(i,\cdots,mid+1),\texttt{LCA}(mid,\cdots,i) ，然后双指针得出 O(len) 个可能的区间更新答案。（求 LCA 可以使用 dfs 序做到 O(n\log n)-O(1)，但是直接树剖求就是均摊正确的了，常数还小/fn。）

注意到如果答案不在这里的话一定顶到了左右端点，使用自己喜欢的方法更新一下即可。例如找到 dfs 序最小和最大值取 LCA。

对于完全包含当前这个区间的情况，只要把小区间长度为 i 的时候的答案记录下来即可，可以用这个区间的 O(len) 个答案和左右的答案合并。

按照线段树的分析可以得到时空复杂度 O(n\log n)。

代码暂时没有。