传送门:https://www.luogu.com.cn/problem/P3177

题意:给你一棵带边权树，染k个黑点，n - k 个白点.问你同色点两两之间的路径和最大为多少.

思路：


这样以来，我们可以将一颗子树的黑点个数看作是背包的体积。然后二元组<子树中黑点个数,点对贡献>就代表着一个物品。对于每个子树来说，只能向根转移一种二元组(黑点个数0~min(子树大小,k)).

问题就转化为树上分组背包，体积恰好为k的最大价值.

第二点:计算点对贡献。

由于这个题目中k是固定了的。所以对于一个子树x.若含有j个黑点，那么x的补集树就含有 k - j 个黑点，白点个数一样。所以贡献为:

第三点:算法流程

使用滚动数组temp。对于一个新增的子树X，外层枚举当前X的补集的黑点个数,内层枚举X的黑点的个数.

up为题目所要求黑点个数

注意：一定要控制循环上界为树的大小sz。这样才能保证每个点对只在它们的LCA处计算一次.复杂度为O(n^2).

AC代码：https://www.luogu.com.cn/record/37903370