自动搬运

查看原文

来自洛谷，原作者为

	迟暮天复明 #ee82ee

搬运于2025-08-24 22:44:14，当前版本为作者最后更新于2023-01-09 12:24:12，作者可能在搬运后再次修改，您可在原文处查看最新版

自动搬运只会搬运当前题目点赞数最高的题解，您可前往洛谷题解查看更多

以下是正文

大家猜测一下这个湖是什么湖。

Subtask 1

特殊限制：$n\le 100,p\le 20$。

直接每个点开始爆搜即可。只要实现的不是太烂，基本上都能通过。

Subtask 2,3

特殊限制：$n\le 1000,p\le 100$ 和 $m=1$。

观察从每个点开始爆搜的时候，从点 $u$ 到点 $v$ 的距离是不变的。所以，我们可以得到一个结论：在某一个可以做减法的时刻，是否选择做减法，对后面能不能做减法是没有影响的。于是选择贪心法，从 $s$ 中的每个点开始搜索，但是只记录最小答案。时间复杂度 $O(nm)$。

Subtask 4

特殊限制：$p=1$。

$p=1$ 保证了我们可以随时随地做减法。

观察到一个性质：在树上从任意点 $u$ 走到任意点 $v$ 的过程中，经过的点的深度先单调递减，后单调递增。就是说只会有一个向根节点走的过程和一个向叶子节点走的过程。那么就可以两个过程分开考虑了。设 $f_i$ 是第一个过程中走到点 $i$ 的最优解，$g_i$ 是第二个过程中走到 $i$ 的最优解，那么就有 $f_i=\min\{f_v+w,0\},g_i=\min\{g_u+w,f_u+w,0\}$。但是有一个问题，就是我们要防止形如 $v\to u\to v$ 的一个过程，所以我们在转移 $f$ 数组的时候要记录一个次大值，和最大值是从哪个点转移而来。

两个数组的初始值，显然是正无穷，除了 $s$ 中的点初值为 $0$。

Subtask 5

特殊限制：树是一条链。

链上显然只有全部向下走和全部向上走两种可能。所以上面记录最小值和次小值的做法在这里不需要了。

但是，上面的 $p=1$ 条件在这里没了。因此我们还需要添加一维：从起点到当前点的距离对 $p$ 取模后得到的值。当且仅当这一维的值是 $0$ 的时候才可以做减法。然后直接转移就行了。

Subtask 6

综合上述两个子任务的做法。设 $f_{i,j}$ 是当前在第 $i$ 个点，路径总长对 $p$ 取模得到 $j$ 的最优解。那么首先 $f_{i,j}=\min\{f_{v,j-1}+w\}$。在 $j=0$ 时还有 $f_{i,j}=\min\{f_{i,j},0\}$。注意只有在至少存在一个 $f_{v,p-1}\ne \mathrm{inf}$ 时才可以进行转移。对于 $g$ 的转移类似。然后在转移 $f$ 的时候记录一下次优解即可。

总时间复杂度 $O(np)$，空间复杂度 $O(np)$。可以通过本题。