题目

{% fold 点击显/隐题目 %}

上回说到，小Ho有着一棵灰常好玩的树玩具！这棵树玩具是由N个小球和N-1根木棍拼凑而成，这N个小球都被小Ho标上了不同的数字，并且这些数字都是处于1..N的范围之内，每根木棍都连接着两个不同的小球，并且保证任意两个小球间都不存在两条不同的路径可以互相到达。没错，这次说的还是这棵树玩具的故事！

小Ho的树玩具的质量似乎不是很好，短短玩了几个星期，便掉漆了！
“简直是一场噩梦！”小Ho拿着树玩具眼含热泪道。
“这有什么好忧伤的，自己买点油漆刷一刷不就行了？”小Hi表示不能理解。
“还可以这样？”小Ho顿时兴高采烈了起来，立马跑出去买回来了油漆，但是小Ho身上的钱却不够——于是他只买回了有限的油漆，这些油漆最多能给M个结点涂上颜色，这就意味着小Ho不能够将他心爱的树玩具中的每一个结点都涂上油漆！

小Ho低头思索了半天——他既不想只选一部分结点补漆，也不想找小Hi借钱，但是很快，他想出了一个非常棒的主意：将包含1号结点的一部分连通的结点进行涂漆（这里的连通指的是这一些涂漆的结点可以互相到达并且不会经过没有涂漆的结点），然后将剩下的结点拆掉！

那么究竟选择哪些结点进行涂漆呢？小Ho想了想给每个结点都评上了分——他希望最后留下来，也就是涂漆了的那些结点的评分之和可以尽可能的高！

那么，小Ho该如何做呢？

每个测试点（输入文件）有且仅有一组测试数据。 每组测试数据的第一行为两个整数N、M，意义如前文所述。 每组测试数据的第二行为N个整数，其中第i个整数Vi表示标号为i的结点的评分 每组测试数据的第3~N+1行，每行分别描述一根木棍，其中第i+1行为两个整数Ai，Bi，表示第i根木棍连接的两个小球的编号。 对于100%的数据，满足N<=10^2，1<=Ai<=N, 1<=Bi<=N, 1<=Vi<=10^3, 1<=M<=N 小Hi的Tip：那些用数组存储树边的记得要开两倍大小哦！
对于每组测试数据，输出一个整数Ans，表示使得涂漆结点的评分之和最高可能是多少。
10 4 370 328 750 930 604 732 159 167 945 210 1 2 2 3 1 4 1 5 4 6 4 7 4 8 6 9 5 10
2977
{% endfold %}

题解

可以用 dp[i][j] 表示包括节点 i 在内一共能涂 j 种颜色能达到的最大满意度

则有 dp[i][j] = max{ dp[child_1][m_1] + dp[child_2][m_2] + …… + dp[child_n][m_n] }
其中 sum{m_1,m_2,……,m_n} = j

很不幸,m_i 的组合非常多,枚举出来肯定会超时
那么我们应该怎么处理这里呢?

重新描述下现在面临的问题:

一个节点有多个子节点,每个按照不同的比例来给子节点分配权重,找出最大的和

对于每一个子节点,可以分配给它最多为 j 的权重
在范围内可以看作无限分配

很像完全背包问题

可以将 j 作为背包容量,m_i 看作选取的个数(体积为1)
而重量则是 dp[child_i][m_i]

首先来看完全背包的模板,这是已经维度压缩后的,而在树形dp中,由于计算顺序不是那么有规律,往往不能压缩

void CompletePack(int cost,int weight) {
    for (int i = cost; i <= v; i++)
        dp[i] = max(dp[i],dp[i - cost] + weight);
}

再看压缩前的算法

dp[i][j] = max{ dp[i][j-c[i]]+w[i] , dp[i-1][j] }

其中 dp[i][j] 表示前i个物品在最大体积为j的情况下的最大价值

dp[i][j] = dp[i][j-m_i]+dp[child][m_i]
与通常的背包问题不同的是,这里由于选取的个数和价值之间不是单纯的线性关系(这就是《背包九讲》中提到的泛化物品),因此不能直接按照原有的方式递推

这里只能枚举m_i
m_i 是 1~m-1 的数,不为0是因为没有意义,不为m是因为根节点需要占用一个涂色名额

我们可以把每一种情况看作一个新的物品
那么我们就获得了一群,价值为dp[child][m_i],体积(花费)为m_i的物品
然后转变成了01背包问题

最外层循环按照01背包的形式,从大到小循环
内层要从小到大循环
因为01背包需要从大到小循环,而dp[x][i]需要用到dp[x][i-j],只有j从小到大才行

for (int i = m; i > 1; --i) 
    for (int j = 1; j < i; ++j) 
        dp[x][i] = max(dp[x][i], dp[x][i - j] + dp[*child][j]);

代码

{% fold 点击显/隐代码 %}```cpp 刷油漆 https://github.com/OhYee/sourcecode/tree/master/ACM 代码备份
#include
#include
#include
using namespace std;

#define Log(d, format, ...)

const int maxn = 105;

int w[maxn];
vector children[maxn];
int dp[maxn][maxn];
int n, m;

void init() {
for (int i = 0; i <= n; i++)
children[i].clear();
memset(dp, 0, sizeof(dp));
}
void addEdge(int u, int v) { children[u].push_back(v); }

void dfs(int x) {
vector::iterator child = children[x].begin();
while (child != children[x].end()) {
dfs(*child);
for (int i = m; i > 1; --i) {
for (int j = 1; j < i; ++j) {
dp[x][i] = max(dp[x][i], dp[x][i - j] + dp[*child][j]);
Log(0, "dp[%d][%d]=%d\n", i, j, dp[i][j]);
}
}
++child;
}
}

int main() {
while (scanf("%d%d", &n, &m) != EOF) {
init();
for (int i = 1; i <= n; i++)
scanf("%d", &dp[i][1]);
for (int i = 1; i < n; i++) {
int u, v;
scanf("%d%d", &u, &v);
addEdge(u, v);
}
dfs(1);
printf("%d\n", dp[1][m]);
}
}

{% endfold %}