自动搬运

查看原文

来自洛谷，原作者为

	Sampson_YW 你弱归你弱，YW比你弱。

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

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

以下是正文

不好意思，我应该声明一下这个做法不是正解的（我不会证明/证伪复杂度）。看见有人被误导了。。

枚举直径端点 $(x,y)$，将 $x\to y$ 这条路径提取出来做区间 DP。

具体地，设 $f_{t,l,r}$ 表示用了 $a$ 序列用了前 $t$ 个数，区间 $[l,r]$ 中的边已经填好了。那么这个区间的子树里的所有点都可以用来放垃圾。

记 $s_{l,r}$ 表示区间 $[l,r]$ 去掉枚举的直径上的点后的大小，那么当 $s_{l,r}>t-(r-l)$ 时 $f_{t,l,r}$ 可以转移到 $f_{t+1,l,r}$。

还有两种转移是 $f_{t,l,r}+a_{t+1}\to f_{t+1,l-1,r}$ 和 $f_{t,l,r}+a_{t+1}\to f_{t+1,l,r+1}$，表示区间向左/向右扩展。

这样是 $O(n^5)$ 的，但是注意到直径端点只需要枚举叶子，再对 $s$ 数组相同的记忆化一下就可以过了。

code