题目

在一棵树上有n个节点(从0开始)，在每个节点上都有一些苹果，现在需要在这棵树上把一些苹果从一个节点搬到另一个节点，使得这些节点上的苹果数的方差最小，从a节点搬运x个苹果到b节点的花费为x*dist(a,b)，求满足条件的最小花费是多少？

思路

想了很久。。。

一开始发现，对于一个节点而言，其上最终的苹果数一定是平均数（取整后的）或是平均数+1，我们定义前者为情况1，后者为情况2，这样我们就可以把方差这一维消掉。

之后，我们跑一个分组背包。

$dp[i][j]$表示当前节点中，情况2的点的个数。

我们看得不是点的贡献，而是每条边的贡献（这也是在处理树上路径问题点权决策复杂的基本套路）。

接下来就是初值的问题，对于叶子节点而言，dp的值显然都是0（此子树内部的边不发生代价）。

那么对于非叶子节点来说呢？

我们无法简单地赋一个初值给它，因为这个节点的所有信息显然都是来自它的子孙的，但如果我们不赋初值，那么dp就没法更新。

所以，对于dp[x][0]和dp[x][1]我们分别表示，对于x自身，把它变成1情况和2情况的最小花费。而这是不需要花费的，所以，我们把这两个dp赋成0，本层就可以更新了。

但是，dp[x][0]和dp[x][1]表示的不仅仅是它自己的状态，也包含了子树中的解，所以我们不能把它当做最终的结果，它的存在，只是为了能让自己和其他的解进行更新，所以要先开一个tmp，最后再赋回去。

阅读更多……