如果您 90 分且样例没过
查看原帖
如果您 90 分且样例没过
520333
SunnyYuan楼主2024/8/12 15:59

这个题目如果按照普通的树性背包来考虑,直接倒序枚举,就会出错,原因就是没有考虑 m=2m = 2 时 fu,0,0f_{u, 0, 0} 的处理。

当 m=2m = 2 时,fu,0,0f_{u, 0, 0} 应该为子树内所有边的边权之和,因为整个子树不准分配给最大的那个头,那就只能由另外一个头全部吃掉了,这时所有的边的两个端点都是由同一个头吃掉的。

而我们理所当然地认为 fu,0,0=0f_{u, 0, 0} = 0,这就导致了错误,以至于后面的所有状态的更新都是错误的。

这也是为什么临时树组赋值无穷大以后不会再初始化 tmp0,0tmp_{0, 0} 和 tmp1,1tmp_{1, 1} 的原因。

2024/8/12 15:59
加载中...