P6071『MdOI R1』Treequery是什么？

P6071 『MdOI R1』Treequery 简单分讨题。 若 \([l, r]\) 内的点全部在 \(p\) 子树内： 考虑找到 \(q = \operatorname{LCA}(l, l + 1, \cdots, r - 1, r)\)，显然 \(q\) 也在 \(p\) 子树内，那么答案为 \(\operatorname{dis}(p, q) = dep_q - dep_p\)。 若 \([l, r]\) 内的点一部分在 \(p\) 子树内，一部分在外面： 显然，此时答案为 \(0\)。 否则若 \([l, r]\) 内的点全部都在 \(p\) 子树外： 显然我们先应该找到 \(q \in [l, r], \operatorname{LCA}(p, q)\) 中深度最深的那个点 \(q\)。 转化一下，即我们只用找到一个点 \(q\)，满足 \(q\) 是 \(p\) 祖先且 \(q\) 子树内包含 \([l, r]\) 中其中一个点即可且是满足这些条件中最深的，可以倍增暴力跳然后判断。 然后需要继续特判：若 \(q\) 子树内包含了所有的 \([l, r]\)，那么令 \(R = \operatorname{LCA}(l, l + 1, \cdots, r - 1, r)\)，故 \(R\) 肯定在 \(q\) 子树内，答案为 \(\operatorname{dis}(p, R) = dep_p + dep_R - 2dep_q\)。否则只有一部分在 \(p\) 子树内，其它的在外面，则答案为 \(\operatorname{dis}(p, q) = dep_p - dep_q\)。 然后说一下如何判断 \(p\) 子树内有多少个点在 \([l, r]\) 范围内，考虑差分为 \([1, r] - [1, l - 1]\)，然后只需要考虑前缀；考虑使用主席树，即 \(T_i\) 维护了编号为 \([1, i]\) 的点的时间戳序列，\(T_i \to T_{i + 1}\) 只需要单点修改 \(dfn_{i + 1}\) 即可；查询则在 \(T_r\) 与 \(T_{l - 1}\) 查询区间 \([dfn_p, dfn_p + siz_p - 1]\) 和即可。 哦，还有个查询区间 \(\operatorname{LCA}\)，可以转化为相邻 \(\operatorname{LCA}\) 中深度最小的那个，那么使用 ST 表即可做到单 \(\log\)。 套上倍增，时间复杂度为 \(O(N \log^2 N)\)，空间复杂度为 \(O(N \log N)\)。