CF1859F Teleportation in Byteland

发现最优策略一定是在一个位置训练，之后就直接到目标点，那么我们可以枚举训练次数，之后就可以转了。那么也就是说我们希望找到一个 \(u,v\) 路径上的点 \(s\)，那么我们之后一定是从 \(s\) 出发，找到最近的一个训练点，训练之后返回 \(s\)。那么我们可以先跑最短路求出每一个点完成这个距离的值 \(f(s)\)。那么之后的答案就是拆贡献相当于是枚举 \(\min(D_0(u,s)+f_i(s)+D_i(s,v))\) 。这个东西可以转成：

\[d_0(u)+d_0(s)-2d_0(l(u,s))+f_i(s)+d_i(s)+d_i(v)-2d_i(l(s,v)) \]

那么我们分 \(s\) 在 \([u,l(u,v)]\) 上和在 \([l(u,v),v]\)，上就有：

\[d_0(u)+d_0(s)-2d_0(s)+f_i(s)+d_i(s)+d_i(v)-2d_i(l(u,v)) \]

\[=d_0(u)+d_i(v)-2d_i(l(u,v))+(-d_0(s)+f_i(s)+d_i(s)) \]

与

\[d_0(u)+d_0(s)-2d_0(l(u,v))+f_i(s)+d_i(s)+d_i(v)-2d_i(s) \]

\[=d_0(u)-2d_0(l(u,v))+d_i(v)+(d_0(s)+f_i(s)-d_i(s)) \]

那么之后发现前面的固定，后面的都只与 \(s,i\) 有关所以维护 \(\log\) 个树剖线段树即可。

\[\]