关于树上背包
  • 板块学术版
  • 楼主LargeRice16pro
  • 当前回复1
  • 已保存回复1
  • 发布时间2025/7/26 23:30
  • 上次更新2025/7/27 00:02:06
查看原帖
关于树上背包
225100
LargeRice16pro楼主2025/7/26 23:30

之前一直知道树上背包有个泛化物品优化,是 O(nV)O(nV) 的。

但是今天在做 ABC F 的时候因为忘记了泛化物品优化怎么写,写的是 O(nV2)O(nV^2)

但是刚才回去复习的时候发现,【选课】的树上背包是要选择 xx 到根上的所有点,ABC F 可以是到根不连续的。

所以泛化物品优化的 O(nV)O(nV) 的树上背包,是专指“选 xx 到根的路径”情形下的背包吗?

也就是一般形式下的树上背包还是 O(nV2)O(nV^2) 的吗?

2025/7/26 23:30
加载中...