题目要求共有n个结点，将其中k个点染成黑色（本题解中为了方便描述，通称所有未染色的点为白点），求黑点两两距离及白点两两距离，使他们之和最大。

我们可以将距离转化为路径，然后再将路径拆分成边，就可以记录每条边被经过的次数，直接计算即可。

问题来了！：那么每条边会对答案贡献多少呢？

我们不妨设这条边的一侧共有w个点，其中有t个点被染成黑色了；

那么这一侧共有t个黑点，（w-t）个白点；类似，另一侧有（k-t）个黑点，（n-w-k+t）个白点；

令sz为这条边的边权，那么贡献就是val=sz*(t*(k-t)+(w-t)*(n-w-k+t));

解题的大致思路就是计算每条边对答案的贡献，最后利用状态转移方程求出最优解。

首先给出状态数组：f[x][y];

f[x][y]表示给以x为根结点的子树染上y个点所得的对于整棵树的最大贡献；

方程如下：

f[i][j]=max(f[i][j],f[i][j-t]+f[z][t]+val);(z表示i的子结点)

目标状态：f[1][k];

最后附上代码

PS:中间可能遇到非法情况，建议把f[x][y]预处理成非法情况，方便跳过处理（代码最后有针对这点的样例，可自行调试）；

强烈建议参考代码理解！！！！！

Over.

(第一次写题解，不足之处请大家多多包涵》_《)