ziiidan
2019-09-18 09:15:23
Update：2020.1.10 更新了关于转移顺序问题的讲解，感谢 popo对于本博客不严谨之处的指出
一道很好的树形DP题。
我这道题思考了半个多小时，没有想出一个可以进行转移的思路，于是开始看题解，由于我在树形DP这方面比较菜，看了好几篇后还是有一些地方不太理解，但功夫不负有心人，在努力了一个晚上后，最后理解了之前不理解的地方并A掉了这道题。
下面开始讲解：
题目大意：
给您一棵有 n 个点的树，树上的边有边权，让你在其中选择出k个黑点，其余的为白点，使得黑点与黑点的距离总和与白点和白点的距离总和的和最大， 让您求出这个值最大是多少。
做题思路剖析：
1.有的同学可能会想到贪心的思路，但是树上路径的贪心会在儿子节点较多的时候情况非常复杂，并且白色节点与黑色节点如何选择位置又是一个好像没有办法解决的问题，代码难度大，正确性也无法保证，所以我们先不考虑这种思路
2.树形DP，在刚刚想到这个思路的时候可能会发现这道题的状态转移没有想象中的容易，首先，在设计状态上，有可能会想到以 i 的子树中选择 j 个黑点到 i 点的最大距离，在 dfs 过程中直接计算答案，但是仔细思考会发现这样的实质还是一种贪心，没有办法保证黑点和白点的贡献和最大。
所以我们在考虑多种状态后选出一种容易转移且可以保证正确性的状态，我选择的是 f[x][j] 表示以 x 的子树中选择 j 个黑点对于答案的最大贡献，那么，这个问题就转换成了一个树上的背包问题，即对于节点 x 每一个子节点 y 的子树 ，都可以选择若干个黑点（可以一个也不选择）（当然，x 节点也可以是黑点），这道题的答题思路大体如此。
3.统计答案，将题目中的统计答案变形，变成统计每一条边的边权乘上两边的黑点数量与边权乘上两边的白点数量的值的和，这个转化很好想，仔细思考下。
接下来是重点！！！
（推荐把接下来的两个问题看完，因为其中有一些东西需要体会）
两个问题：转移顺序问题 和 不合法情况去除问题
一. 转移顺序问题
我们在第一层的转移中，为了保证不重复转移（跟01背包压掉一维后的倒序转移一样），我们倒序转移。
在第二层的转移顺序的问题上，我认为：
1.正序转移和倒序转移在本质上并没有差别，但是在这道题中，对于当前枚举的子节点的子树，哪怕一个黑点也没有，它仍然可以对答案产生贡献，所以我们要先算上这种情况的贡献，否则在接下来的转移中，就会少计算本来就有的价值，从而答案错误。
2.正序枚举的好处在于，它会先枚举在当前枚举的子节点的子树中一个黑点也没有的情况，从而直接加上这种情况的贡献（不明白的话可以对着代码模拟一下就可以明白了），转移就变得比较方便。
3.第二层正序枚举为什么不会重复转移的问题在这里说一下，我们发现，我们第二层的枚举一直是在转移同一个状态（即我的代码中的 f[x][j] ），所以正序并不会用被当前枚举的子节点更新过的信息，所以并不会重复转移。
3.再来说说倒序，首先，倒序的正确性是可以保证的，但是在这道题中，一个黑点也不选的情况下，只要子树的大小改变，价值就会改变，所以当我们枚举到一个新的子节点的子树的时候，我们当前点的子树的大小会被这个新枚举的子节点的子树的大小所更新，但此时在我们的数组中，保存的仍然是子树大小没有被更新时的价值，所以我们要优先将其更新，具体代码实现可以看看 子谦。写的题解，我认为写得比较清晰。这样的话，倒序枚举也是丝毫没有问题的。
我认为神仙 popo 所说的更好理解，引用一下：
神仙popo：“但是这道题比较特殊，就是我们的ｋ可以等于０，这就导致对 于每一个ｊ，最后一个ｋ一定会进行一次非法转移。通俗点讲， 最后一个转移是：f[u][j]=max(f[u][j],f[u][j]+f[v][0]+val); 这转移肯定会发生，并且我们用的来源状态f[u][j-k]由于ｋ=0的 原因，已经不满足我们原本要求的“我们需要的原状态不会被在这 之前更新”了，因为f[u][j]已经不知道被更新多少次了。”
“当然为此我们下面就不能去计算ｋ=0的转移了。 ”
二. 不合法情况去除问题
1.在我的代码中（下面有），我在刚开始的时候吧答案数组（即 f 数组）全部赋值了-1，-1表示这个状态不合法，我在程序刚开始的售后并不知道哪些状态合法，所以我先都赋值为-1，在DP的过程中发现合法的状态在改变它的值。
2.在我的代码的第二层循环中，我特判了 f[x][j - k] 的值为-1的情况，因为在我的枚举中，有可能会出现一种之前的最多黑点值不够转移的情况，请看如下这个例子：
比如说我们枚举在当前的子节点的子树中，我们枚举它里面有1个黑点，那么我们需要一个在其他子树中选了共 j - 1 个黑点的状态，但是如果其他的子树的大小总和还不到 j - 1 的话，那么这个状态显然是不合法的，所以我们要去除这种情况。
我们以上的例子扩宽一下，就可以得到如下策略：
我们枚举在当前的子节点的子树中，我们枚举它里面有k个黑点，那么我们需要一个在其他子树中选了共 j - k 个黑点的状态，但是如果其他的子树的大小总和还不到 j - k 的话，那么这个状态显然是不合法的，所以我们要去除这种情况。
至此，这道题的策略讲解就结束了，在我的代码中还有一些解释，如果没有理解的话，可以再看看。
这是我的代码：
（因为我循环中一般用k，所以题目中的 k 在我的代码中为 m，望理解）
#include<iostream>
#include<cstdio>
#include<cstring>
using namespace std;
const int maxn = 2005;
struct Edge{
int x, y, w, nxt;
}e[maxn << 1 | 1];
int n, m, cnt;
int fr, to, haj;
int head[maxn], siz[maxn];
long long f[maxn][maxn];
inline int read(void)
{
int s = 0, w = 1;
char ch = getchar();
for(; ch < '0' || ch > '9'; ch = getchar()) if(ch == '-') w = -1;
for(; ch <= '9' && ch >= '0'; ch = getchar()) s = s * 10 + ch - '0';
return s * w;
}
inline void add(int x, int y, int w)
{
e[++cnt].x = x;
e[cnt].y = y;
e[cnt].w = w;
e[cnt].nxt = head[x];
head[x] = cnt;
}
void dfs(int x, int father)
{
siz[x] = 1; // 初始化子树的大小，因为有本身这个点，所以大小赋值为 1
f[x][0] = f[x][1] = 0; // 无论在什么情况下，不选和只选一个这两种情况一定合法，所以把值赋成 0，在下面更新
for(register int i = head[x]; i != -1; i = e[i].nxt)
{
int y = e[i].y;
if(y == father) continue; // 加边加的是双向边，防止出现因回到自己的父亲而死循环或者错误转移的情况
dfs(y, x); // 递归求解
siz[x] += siz[y]; // 更新当前点子树的大小
for(register int j = min(m, siz[x]); j >= 0; j--) // 最大取值为最多取的黑点的数量的子树大小的更小值， 再大的状态意义不合法
{
for(register int k = 0; k <= min(j, siz[y]); k++) // 同上，由于是要更新的状态的黑点数量为 j，所以在这个枚举中的上限要和 j 取更小值
{
if(f[x][j - k] == -1) continue; // 特判掉不合法的情况
long long val = 1ll * e[i].w * k * (m - k) + 1ll * e[i].w * (siz[y] - k) * (n - m - siz[y] + k); // 这是新产生的贡献，由于很长的缘故，单独写出来
f[x][j] = max(f[x][j], f[x][j - k] + f[y][k] + val); // 看是否能够更新答案
}
}
}
}
signed main()
{
memset(head, -1, sizeof(head));
memset(f, -1, sizeof(f)); // 答案数组的预处理
n = read(); m = read();
for(register int i = 1; i < n; i++)
{
fr = read(); to = read(); haj = read();
add(fr, to, haj); // 加双向边
add(to, fr, haj);
}
dfs(1, 0); // 递归求解
cout << f[1][m] << '\n';
return 0;
}这篇题解即暂时告一段落了，有什么问题的话直接在讨论区问或着洛谷私信均可。
谢谢阅读。