请忽略$f$数组定义那里的注释
by ctj12461 @ 2021-09-16 00:25:02
查表法复杂度是假的（在所有树形背包中都是），会被链的情况卡，所以要用刷表法
by conprour @ 2021-10-26 11:50:26
考古，查表钟爱者也T#4（
by jjsnam @ 2022-07-11 16:55:35
查表法也可以过.不过要注意枚举从当前子树取的个数j下界可能大于0.
j的下界应该取max(0,i-(size[i]-size[j]),例如前面子树总计能凑出5个,当前子树能凑出3个,在计算dp[8]时,不需要从dp[6]和dp[7]转移过来(因为前面子树凑不出6个或7个).
可以参见https://www.luogu.com.cn/discuss/291866 中的4楼,他只是把楼主的代码的第52行的循环下界从1改成了j-siz[now]+siz[p]).
这样查表法和刷表法的复杂度就是一样了,把"写错的查表法"(指循环下界无脑从0开始)的假复杂度改正过来了.
这一点我觉得是个比较惊讶的发现,我是被这题的样例4搞TLE看了上面的链接才发现的.
by laozhu1234 @ 2023-03-16 17:56:28