同步发表于博客园。

显然每个点一定被祖先覆盖。

设 $dp_{i,j,k}$ 表示 以 $i$ 为根的子树，$i$ 的亮度为 $j$（$j<$ 以 $i$ 为根的子树深度），最深的没被照亮的点深度为 $k$ 的最小代价。转移考虑将 $j$ 次漂流分配到其所有儿子中，对于每一种分配求和并取最小值。

对于 $k$ 这一维我们发现是独立的，所以可以对每组 $i,j$ 做取前缀最小值从而做到 $O(n)$。而 $i,j$ 两维的结构是一个树上背包，显然可以做到 $O(n^2)$，因此总复杂度 $O(n^3)$ 可以通过 $n\le 700$。