P9846

Sampson_YW · 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