洛谷3117 BZOJ4033 树上染色 树形背包
题目链接 题意: 给你一棵n个点的数,边有边权,要在其中选k个点染成黑色,其余点染成白色,求所有相同颜色点之间的路径的权值之和。题解: 这个题不难想到要树形dp,状态设计也还好,但是要如何设计dp含义、如何统计答案是有难度的。我们不难想到dp有一维应该设计成以x为根的子树的情况,另一维设计成子树内染了i个黑色点,但是如果dp数组的含义设为子树内的权值之和的话似乎好像很难向父节点转移,因为...