date: 2021.02.05 ??:??-??:??

practice link

题目大意：给一棵树，每次询问删掉两条边，问剩余森林的直径。

题解：考虑维护 dfs 序上的区间直径。给一个点集 $S$，设其最远两点分别为 $x,y$。考虑树上任意一点 $z$ 和 $S$ 中任意一点 $w$。若 $\text{dis}(z,w)$ 严格大于 $\text{dis}(z,x)$ 和 $\text{dis}(z,y)$，考虑 $x$ 到 $y$ 的路径。若 $z$ 到 $w$ 的路径在 $x$ 到 $y$ 的路径上经过 $v_{1}\to v_{2}\to\ldots\to v_{t}$，且 $t\ge2$，不妨设 $v_{1}\to v_{t}$ 对应了 $x$ 到 $y$ 的方向。那么 $z$ 到 $y$ 的路径必然是 $z\to v_{t}\to y$。由于 $z$ 到 $w$ 的距离更大，因此 $\text{dis}(x,w)>\text{dis}(x,y)$，矛盾。若 $z\to w$ 不经过 $x\to y$，同理也可证。因此 $z$ 到 $S$ 的最大距离必然要选择 $x,y$ 中的一点。那么一个简单的推论就是，若有两个集合 $S_{1},S_{2}$，那么 $S_{1}\cup S_{2}$ 的直径必然是从 $x_{1},y_{1},x_{2},y_{2}$ 中选择 $2$ 个点，即需要判断 $6$ 次。这样一来，就可以使用 ST 表维护区间直径了。