给定一棵 \(n\) 个节点的树与 \(q\) 次询问，每次询问给出一个 \(x\) 与一个大小为 \(k\) 的点集 \(a\)，要求求出在删去了 \(a\) 中的点后从 \(x\) 出发的最长简单路径的长度。每次询问独立。
\(n, q, \sum k \le 2 \times 10^5\)。
一些记号：
- \(p_i\) 表示时间戳 \(i\) 对应的节点
- \(c_u\) 表示节点 \(u\) 的时间戳
- \(s_u\) 表示节点 \(u\) 的子树大小
- \(d_u\) 表示节点 \(u\) 的深度
- \(\operatorname{in}(u) = c_u\)，即在 DFS 过程中进入节点 \(u\) 的时间
- \(\operatorname{out}(u) = c_u + s_u - 1\)，即在 DFS 过程中离开节点 \(u\) 的时间
- \(\operatorname{nxt}(u, v)\) 表示在 \(u \to v\) 的路径上的第二个节点，其中 \(u\) 为 \(v\) 的祖先。
思考「删点」这个过程的本质，可以发现，若以每次询问的 \(x\) 作为根节点，那么删点本质上就是使得某个点以及其子树内的点都无法被访问到，而「子树」这一条件则很容易让我们想到 DFS 序。于是删除点 \(u\) 也就是意味着 DFS 序处在 \([\operatorname{in}(u), \operatorname{out}(u)]\) 的节点无法被访问了。
但是如果以每次询问的 \(x\) 作为根节点，那就相当于每次询问都要重新构造 DFS 序，复杂度肯定是爆炸的，因此我们考虑如何在根节点固定为 \(1\) 的情况下表示上述的过程。
画一个图，我们就很容易得到：对于一个点 \(u\) 以及一个待删除的点 \(v\)，我们很容易发现，若 \(v\) 为 \(u\) 的祖先，那么删去 \(v\) 会导致除去 \(\operatorname{nxt}(v, u)\) 所在的子树外，其他的节点，也就是 DFS 序位于 \([1, \operatorname{in}(\operatorname{nxt}(v, u)) - 1]\) 以及 \([\operatorname{out}(\operatorname{nxt}(v, u)) + 1, n]\) 的节点，都无法被访问了。而如果 \(v\) 不是 \(u\) 的祖先，那么跟根不固定的情况没有区别，都是 DFS 位于 \([\operatorname{in}(v), \operatorname{out}(v)]\) 的节点无法被访问到。
那么很容易看出，「删点」这一操作会将可访问的点的 DFS 序划分成个数为 \(\mathcal{O}(k)\) 级别的连续段，而 \(\sum k \le 2 \times 10^5\)，因此我们只需要一个能够快速求出每个连续段内的答案的方法即可。
对于一个节点 \(u\)，我们设 \(f_i = \operatorname{dis}(p_i, u)\)，那么一次询问的答案就是在 \(x\) 可访问的节点对应的 DFS 序中 \(f\) 的最大值。对于根节点 \(1\)，很显然有 \(f_i = d_{p_i}\)。对于节点 \(u\) 与它的一个儿子节点 \(v\)，不难发现，对于 \(v\) 子树外的点，也即是 DFS 序位于 \([1, \operatorname{in}(v) - 1]\) 与 \([\operatorname{out}(v) + 1, n]\) 的点，其到 \(v\) 的距离为到 \(u\) 的距离 + 1，而对于子树内的点，其到 \(v\) 的距离则为到 \(u\) 的距离 - 1。那么这实际上就是在 \(f\) 上做区间加减的操作，而求答案则对应着区间求 \(\max\) 的操作，因此可以用一棵线段树维护。
那么做法就很简单了。我们考虑将询问离线，然后在 DFS 的过程中计算每个询问的答案。在转移到当前节点儿子的时候就用上述的方法来维护当前的 \(f\) 就可以了。
最后的问题就是如何得到某个询问对应的可访问的连续段。这个是经典的了，我们考虑把不合法的连续段求出来，然后按照左端点为第一关键字排序，再在扫描过程中维护当前可访问连续段的左端点即可。
代码，时间复杂度大概是 \(\mathcal{O}((\sum k + n) \log n)\)。
标签：访问,询问,Tree,DFS,节点,CF1904E,Queries,operatorname,out From： https://www.cnblogs.com/forgot-dream/p/17892861.html