BZOJ4033 - Click Here
Description
有一棵点数为N的树，树边有边权。给你一个在0~N之内的正整数K，你要在这棵树中选择K个点，将其染成黑色，并将其他的N-K个点染成白色。将所有点染色后，你会获得黑点两两之间的距离加上白点两两之间距离的和的收益。
问收益最大值是多少。
Input
第一行两个整数N,K。
接下来N-1行每行三个正整数fr,to,dis，表示该树中存在一条长度为dis的边(fr,to)。
输入保证所有点之间是联通的。
N<=2000,0<=K<=N
Output
输出一个正整数，表示收益的最大值。
Solutions
从点的角度不好计算，考虑从边的角度进行考虑。
对于边$(u,v)$，其对答案产生的贡献显然为$dis(u,v) \times (b_u \times b_v + w_u \times w_v)$，其中$b_i,w_i$分别表示以$i$为根的子树中，黑色/白色节点数。
根据上诉结论，容易得到一个树形DP。
设$f(i,j)$表示以$i$为根的子树中，有$j$个黑色节点的最大收益。
其转移方程为$f(x,i)=\left\{ \, f(son,j)+f(x,i-j)+val(x,son,j) \, \right\}_{max}$，其中$val(i,j,k)$表示以$j$为根的子树有$k$个黑色节点时，$(i,j)$对答案的贡献。
这个DP暴力转移是$O(n^3)$的。
但事实上，在转移过程中，有效状态是很少的。如果只枚举有效状态的话，可以保证时间复杂度为$O(n^2)$。
至于证明的话，可以对每个根节点进行分析。当合并一个子树的时候，代价为已经合并的子树大小*当前子树的大小。代价在数值上等价于满足$lca(i,j)=root$的数对数，因此$O(\sum_x \sum_i \sum_j [lca(i,j)=x])=O(n^2)$。
时间复杂度$O(n^2)$
CODE
CODE - Click Here