#4033. [HAOI2015]树上染色

传送门

有一棵点数为 NN 的树，树边有边权。给你一个在 00 ~ NN 之内的正整数 KK ，你要在这棵树中选择 KK 个点，将其染成黑色，并将其他的 N−KN−K 个点染成白色。将所有点染色后，你会获得黑点两两之间的距离加上白点两两之间距离的和的收益。

问收益最大值是多少。

SolutionSolution

树形DP是很好看出来的。

但是确定状态并不是那么简单的事情了。

我们先考虑形如 <u,v,w><u,v,w> 的边能够产生什么贡献吧。

题目中描述，你会获得黑点两两之间的距离加上白点两两之间距离的和的收益。那么在 uu 的左侧（很抽象的一个说法，就理解成把这条边摆中间，与 uu 相连的那一部分都摆在左边，把与 vv 相连的都摆在右边，很明显，这两个部分是没有交集的）的黑点（白点同理）和 vv 的右侧的黑点会产生两两配对（每个部分内部的匹配不属于这条边所产生的贡献），结果产生的收益就是 Blacku∗Blackv∗wBlacku∗Blackv∗w ，同理，我们就可以知道这条边能产生的收益可以表述为 (Blacku∗Blackv+Whiteu∗Whitev)∗w(Blacku∗Blackv+Whiteu∗Whitev)∗w 。

接下来就考虑状态，我们可以定义 d(i,j)d(i,j) 表示以 ii 为根的子树中有 jj 个黑点能产生的最大贡献。

有了状态的定义，我们就额外要预处理出 size[]size[] 数组来记录以某个结点为根时它的子树中的结点总和。

现在思路就清晰了。我们可以用 dfs()dfs() 边预处理边跑DP。

dfs()dfs() 中遍历一条边 <u,v><u,v> 结束时，枚举左右两边的黑点个数，计算出它所带来的贡献，将其并入答案。然而枚举也要讲求策略，我们令 pp 是以 uu 为根的子树的黑点数， qq 是以 vv 为根的子树的黑点数。

• Blacku=k−qBlacku=k−q 容斥原理
• Blackv=qBlackv=q 已知条件
• Whiteu=n−size[v]−(k−q)Whiteu=n−size[v]−(k−q) 首先计算出除去以 vv 为根的子树中的结点之后全树还剩 n−size[v]n−size[v] 个结点，再减去其中黑点的数目即 Blacku=k−qBlacku=k−q 。
• Whitev=size[v]−qWhitev=size[v]−q 容斥原理

这样我们的得出来的值是 d(v,q)d(v,q) 而不是 d(u,p)d(u,p) 我们需要用 d(u,p)=max(d(u,p),d(u,p−q)+d(v,q)+val)d(u,p)=max(d(u,p),d(u,p−q)+d(v,q)+val) 来将其并入答案，其中 valval 就是这条边的贡献， d(u,p−q)d(u,p−q) 的意义是 uu 的其他儿子及其子树的最大贡献。

最后，边界条件是 d(u,0)=d(u,1)=0d(u,0)=d(u,1)=0 而其他都是 −1−1 这应该很好理解。

[HAOI2015]树上染色

原文：https://www.cnblogs.com/shenben/p/11603476.html