题解：P12585 「KTSC 2019 R1」广播站

· · 题解

直接记 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}。