自动搬运

查看原文

来自洛谷，原作者为

	Kevin090228 世界存活法则

搬运于2025-08-24 22:53:27，当前版本为作者最后更新于2024-01-08 21:20:17，作者可能在搬运后再次修改，您可在原文处查看最新版

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

以下是正文

通过对题目背景的阅读得知只有一个机器人。所以 DP 状态设计是显然的：$f(i,j,l,r)$ 表示考虑了前 $i$ 次操作，机器人在点 $j$，$j$ 的左右子树内分别有 $l,r$ 个人类的最大产出。

对于操作 $3,4$，转移是简单的，直接 $f(i,j,l,r)\to f(i+1,j,l,r)$ 即可。

这里设辅助数组 $g(u,l,r)$ 表示在机器人移动中，在 $u$ 点，左右子树有 $l,r$ 个的最大产出。要注意机器人必须移动，所以 $g$ 的初值也要转移得到，而不能直接复制。

对于操作 $1$，由深到浅进行树形 DP。不妨设 $u$ 是 $f_u$ 左儿子，有转移：$g(u,a,b)\to g(f_u,a+b,c)$，对于每个 $a+b$ 求出 $g(u,a,b)$ 最大值，然后就能枚举 $c$ 转移了，时间复杂度是树形背包的 $O(n^2)$。

对于操作 $2$，由浅到深进行树形 DP。不妨设 $u$ 是 $f_u$ 左儿子，有转移：$g(f_u,a,b)\to g(u,c,a-c)$，类似地，对于每个 $a$ 求出 $g(f_u,a,b)$ 最大值，然后就能枚举 $c$ 转移，时间复杂度同样是树形背包的 $O(n^2)$。

对于计算采矿的贡献，预处理 $A(u,c),B(u,c)$ 分别表示在 $u$ 子树内/外放 $c$ 个人的最大采矿产出即可。

总时间复杂度 $O(n^2c)$。