题解【CF1307F Cow and Vacation】

感觉 CF*3300 的难度没有这么简单吧（

题目传送门。

考虑 \(\texttt{Bessie}\) 运动的过程：起点 \(\to\) 休息点 $\to $ \(\cdots\) \(\to\) 休息点 \(\to\) 终点。

考虑我们把能相互到达的点放到一个连通块，那么问题就变得简单。

我们对于每一个休息点开始 \(\text{bfs}\)，注意，每个休息点可控制的范围是 \(\frac{k}{2}\) 而非 \(k\)，然后用并查集维护这个连通块。

考虑询问操作：

• 对于询问的两点 \(a,b\)，若 \(\operatorname{dist}(a,b)\le k\)，那么这是可行的。

• 若 \(a,b\) 在同一个连通块里，那么也是可行的。

• 我们考虑将 \(a\) 和 \(b\) 分别沿着 \(a\to b\) 这条路径向上走 \(\frac{k}{2}\) 个点，看看能不能走到一个连通块里。

这个东西的实现可以考虑倍增去跳，如果跳着跳着超出了 \(\texttt{LCA}\)，那么往另一半跳。

往另一半跳的过程不好维护，因为是祖先跳到儿子,设 \(\texttt{LCA}\) 为 \(c\)，考虑超出的距离为 \(k-\operatorname{dist}(a,c)\)，这个东西可以表示成 \(b\) 往上跳 \(\operatorname{dist}(b,c)-\left(k-\operatorname{dist}(a,c)\right)\) 步，也就是 \(b\) 向上跳 \(\operatorname{dist}(a,b)-k\) 步到达的点。倍增即可。

注意半径为 \(\frac{k}{2}\) 不好处理，我们可以在每条边间插一个点，这样将 \(k\leftarrow k\times 2\) 即可。

时间复杂度 \(\Theta(n\log n)\)。

代码比较人性化。