自动搬运

查看原文

来自洛谷，原作者为

	s4CRIF1CbUbbL3AtIAly 僕だって空を飛べる / 雲になっていく / 風になっていく / いつかはみんな / 星になっていく

搬运于2025-08-24 23:16:36，当前版本为作者最后更新于2025-05-24 19:07:12，作者可能在搬运后再次修改，您可在原文处查看最新版

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

以下是正文

直接记 $f_{rt,l,r,d}$ 表示区间 $[l,r]$ 中根为 $rt$，深度为 $d$ 的最小代价。直接做是五次方的，考虑优化。

注意到实际上只需要记录根为 $l$ 和根为 $r$ 的最小代价 $gl,gr$，就有 $f_{rt,l,r,d}=gr_{l,rt,d}+gl_{rt,r,d}$。

$gl$ 和 $gr$ 直接转移都四次方的，于是就做完了。