有一棵点数为N的树,树边有边权.给你一个在0~N之内的正整数K,你要在这棵树中选择K个点,将其染成黑色,并将其他的N-K个点染成白色.将所有点染色后,你会获得黑点两两之间的距离加上白点两两之间距离的和的收益.
接下来N-1行每行三个正整数frtodis,表示该树中存在一条长度为dis的边(frto).
N<=20000<=K<=N
输出一个正整数,表示收益的最大值.
从点的角度不好计算,考虑从边的角度进行考虑.
根据上诉结论,容易得到一个树形DP.
这个DP暴力转移是$O(n^3)$的.
但事实上,在转移过程中,有效状态是很少的.如果只枚举有效状态的话,可以保证时间复杂度为$O(n^2)$.
至于证明的话,可以对每个根节点进行分析.当合并一个子树的时候,代价为已经合并的子树大小*当前子树的大小.代价在数值上等价于满足$lca(ij)=root$的数对数,因此$O(\sum_x \sum_i \sum_j [lca(ij)=x])=O(n^2)$.