之前一直知道树上背包有个泛化物品优化,是 O(nV)O(nV)O(nV) 的。
但是今天在做 ABC F 的时候因为忘记了泛化物品优化怎么写,写的是 O(nV2)O(nV^2)O(nV2)。
但是刚才回去复习的时候发现,【选课】的树上背包是要选择 xxx 到根上的所有点,ABC F 可以是到根不连续的。
所以泛化物品优化的 O(nV)O(nV)O(nV) 的树上背包,是专指“选 xxx 到根的路径”情形下的背包吗?
也就是一般形式下的树上背包还是 O(nV2)O(nV^2)O(nV2) 的吗?