基本上所有的题解, 状态的存放都是二维, 把背包的第一维压缩掉了, 所以好多题解都提到什么正序枚举, 但是这不是核心点.

背包问题, 编码上, 使用滚动数组的技巧相比于压缩掉一维会清晰很多, 也就不需要考虑枚举顺序.

dp的问题, 无外乎, 状态的定义, 转移, 边界.

状态: dp[u][i][j]表示考虑以u节点为根的子树, 其前i个儿子, 染色j个黑色节点, 子树里所有的边, 对整个树而言, 所能获得的受益最大值.

1. 因为子树里的边所获得收益, 是相对于整棵树而言的而不是子树, 也就是大部分题解里说的对答案的贡献.

2. 染色j个黑色节点：包括父节点u + 前i个儿子节点. 这里特别注意不要忘记了父节点u哟.

3. 对于上述状态dp[u][i][j], 如果我们把第一维去掉就变为dp[i][j]了, 考虑前i个儿子, 染色j个黑色节点的最大值. 这个状态是不是就是常见背包问题里的状态, 所以我们管这类题叫树上背包, 在树上做背包.

转移: 枚举第i个儿子节点染色k个黑色节点, 这里可以对k二进制背包优化.

4. <u, v, w> 这条边的贡献 = (这条边的一端的黑色个数 * 这条边的另一端的黑色个数 + 这条边的一端的白色个数 * 这条边的另一端的白色个数) * 这条边的权值

边界: 对于叶子节点, dp[u][0][0] = dp[u][0][1] = 0, 此时只有父节点u, 它可以自己染色为黑色或者不染, 因为没有边所以dp值当然为0. 其它都是非法值, 由于是求最大值, 所以所有非法值可以赋值为无穷小.

时间复杂度: 树上背包问题的时间复杂度较复杂, 看过的一篇时间复杂度分析树上背包的上下界优化, 正确性未知.

参考实现代码, 提交记录

现在本题不开放题解了, 希望对初学树上背包问题的同学一点帮助, peace.