记 fi,j,k 表示距离 i 最近的建了伐木场的祖先为 j,钦定 i 不建造伐木场,i 子树内共建了 k 个伐木场时,i 子树内部不包括 i 的所有点生产的木材产生的最小代价(要算到运到 j 为止)。
记 gi,k 表示钦定 i 建造伐木场,i 子树内共建了 k 个伐木场时,所有 i 子树内生产的木材产生的最小代价(这里 i 子树内所有生产的木材都能在 i 子树内部消化掉)。
记 hi,j,k 表示距离 i 最近的建了伐木场的祖先为 j,i 子树内共建了 k 个伐木场时,i 子树内产生的所有木材在所有情况下可能造成的最小代价,不考虑其它因素。
对于 g,要求第二维大于等于 1。
感觉这个东西理解起来更简单一些,下标和转移方向之类的都没有很绕的地方。
复杂度 O(n4)。