如何卡复杂度不对的树形背包

学术版

Shunpower @ 2025-06-28 11:53:05

众所周知，正确写法的树形背包在第二维是 \mathcal O(c) 的情况下复杂度是 \mathcal O(nc) 的。但是如果上下界不精细就会写成 \mathcal O(nc^2)。

例如

for(int i = 0; i <= c; i++)
  for(int j = 0; j <= siz[y]; j++)

for(int i = 0; i <= siz[x]; i++)
  for(int j = 0; j <= c; j++)

for(int i = 0; i <= siz[x] + siz[y]; i++)
  for(int j = 0; j <= siz[x]; j++)

for(int i = 0; i <= c; i++)
  for(int j = 0; j <= siz[x] + siz[y] - i; j++)

...

如何卡这种写错的树形背包？有一种通用的卡法吗？

by ykzzldz @ 2025-06-28 12:14:17

@Shunpower 链可以卡到复杂度上界

by 035966_L3 @ 2025-06-28 12:24:54

@Shunpower 比如 k 层满二叉树下正确写法是 O(2^k) 而错误写法是 O(3^k)？

by gesong1234 @ 2025-06-28 12:25:43

@Shunpower 先造一个链，然后随机加点分叉，这样防止特判。

by 035966_L3 @ 2025-06-28 12:27:11

@gesong 并不，因为可以先按 size 给儿子排序。

by Loser_Syx @ 2025-06-28 12:33:38

@gesong 这个尿分叉有点搞笑了吧

by Shunpower @ 2025-06-28 12:35:14

@035966_L3 能简单说一下这两个复杂度是怎么分析出来的吗，我不是很懂树形背包的复杂度证明/kel

by Shunpower @ 2025-06-28 12:37:03

@035966_L3

但是链加随机分叉好像可以把

for(int i = 0; i <= siz[x] + siz[y]; i++)
  for(int j = 0; j <= siz[x]; j++)

这种 pull 的代码卡到三方。