【题解】BZOJ 4033 [HAOI2015]树上染色

Description D e s c r i p t i o n

传送门

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

问收益最大值是多少。

Solution S o l u t i o n

树形DP是很好看出来的。

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

我们先考虑形如 <u,v,w> < u , v , w > <script type="math/tex" id="MathJax-Element-51"> </script> 的边能够产生什么贡献吧。

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

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

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

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

dfs() d f s ( ) 中遍历一条边 <u,v> < u , v > <script type="math/tex" id="MathJax-Element-64"> </script> 结束时，枚举左右两边的黑点个数，计算出它所带来的贡献，将其并入答案。然而枚举也要讲求策略，我们令 p p 是以 uu 为根的子树的黑点数， q q 是以 vv 为根的子树的黑点数。

• Blacku=k−q B l a c k u = k − q 容斥原理
• Blackv=q B l a c k v = q 已知条件
• Whiteu=n−size[v]−(k−q) W h i t e u = n − s i z e [ v ] − ( k − q ) 首先计算出除去以 v v 为根的子树中的结点之后全树还剩 n−size[v]n−size[v] 个结点，再减去其中黑点的数目即 Blacku=k−q B l a c k u = k − q 。
• Whitev=size[v]−q W h i t e v = s i z e [ 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 ) = m a x ( d ( u , p ) , d ( u , p − q ) + d ( v , q ) + v a l ) 来将其并入答案，其中 val v a l 就是这条边的贡献， d(u,p−q) d ( u , p − q ) 的意义是 u u 的其他儿子及其子树的最大贡献。

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

Code C o d e

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
#include<cstdio>
#include<cstring>
#include<iostream>
#include<algorithm>
#define max(x, y) ((x) > (y) ? (x) : (y))
#define min(x, y) ((x) < (y) ? (x) : (y))
#define LL long long
#define MAXN 2010
struct edgetype {
int to, next, dist;
}edge[MAXN << 1];
int head[MAXN], cnt;
int n, k, size[MAXN];
LL d[MAXN][MAXN];
inline void AddEdge(int from, int to, int dist) {
edge[++cnt] = (edgetype){to, head[from], dist};
head[from] = cnt;
}
void dfs(int u, int p) {
size[u] = 1;
d[u][0] = d[u][1] = 0;
for (int i = head[u]; i; i = edge[i].next) {
int v = edge[i].to;
if (v == p) continue;
dfs(v, u);
size[u] += size[v];
}
for (int i = head[u]; i; i = edge[i].next) {
int v = edge[i].to, w = edge[i].dist;
if (v == p) continue;
for (int p = min(size[u], k); p >= 0; p--)
for (int q = 0; q <= min(p, size[v]); q++)
if (d[u][p - q] != -1) {
LL val = 1ll * (q * (k - q) + (size[v] - q) * (n - k + q - size[v])) * w;
d[u][p] = max(d[u][p], d[u][p - q] + d[v][q] + val);
}
}
}
int main() {
scanf("%d%d", &n, &k);
for (int i = 1; i < n; i++) {
int u, v, w;
scanf("%d%d%d", &u, &v, &w);
AddEdge(u, v, w);
AddEdge(v, u, w);
}
memset(d, -1, sizeof d);
dfs(1, 0);
printf("%lldn", d[1][k]);
return 0;
}

最后

以上就是仁爱画板最近收集整理的关于【题解】BZOJ 4033 [HAOI2015]树上染色的全部内容，更多相关【题解】BZOJ内容请搜索靠谱客的其他文章。