bzoj4151 The Cave 的一个 idea

原题题面： > 给定一棵有 $n$ 个节点的树，相邻两点之间的距离为 $1$。 > 请找到**一个点** $x$，使其满足所有 $m$ 条限制，其中第 $i$ 条限制为 $\text{dis}(x,a_i)+\text{dis}(x,b_i)\le d_i$。如果无解输出 $\text{NIE}$，否则输出 $\text{TAK}$。 > $\sum n,\sum m\le 3\times 10^5$。 在一场 noip 模拟赛中，Owen 成功把题看错，写了长达 5K 的代码并成功没有调出来。 若再给我半小时我将绝杀（笑）。 第二天，Owen 发现自己的解法可以做加强版，**将一个点改成所有点**，成功把一道找性质的题改成了数据结构题。 myh 在群里分享了所有点 $\mathcal{O}(n)$ 的解法，可是 Owen 并没有听懂，有谁会的话可以来私信我。 ------------ 先将 $d<\text{dis}(a,b)$ 的情况判掉，可以发现，$x$ 满足限制等价于存在 $y\in \text{path}(a,b)$，使得 $dis(x,y)\le \frac {d-\text{dis}(a,b)}2=D$。 那么限制可以分为两部分：子树内和子树外。子树外的限制可以放在 $\text{LCA}(a,b)=lca$ ，即子树外的点与 $lca$ 的距离不超过 $D$。这部分可以用换根 $dp$ 算掉。 接着我们发现，对于 $u\in \text{path}(a,b)$，我们会把限制放在 $v\in son_u\land v\not \in \text{path}(a,b)$，即子树内的点与 $v$ 的距离不超过 $D-1$。 直接暴力放限制显然是 $\mathcal{O}(n)$ 的，考虑优化。 发现仅有 $1/2$ 个 $v\in \text{path}(a,b)$。在 $lca$ 处特判后，就只有一个了。 我们可以用线段树合并或可并堆维护经过某条边限制的最小值，在上传的时候对 $u$ 的其他儿子取 $\min$。 因为 $lca$ 处有两个儿子，代码里使用了线段树，相当于将 $u$ 的儿子排成一个序列，对序列的某几个区间取 $\min$。 最后 $\text{dfs}$ 判一遍即可。 （代码写的是所有点的做法，但因为是 bzoj4151 的代码，只找了一个点） [code](https://www.luogu.com.cn/paste/ddma1kg3)