BZOJ 4033. [HAOI2015]树上染色（树形DP，边贡献）

本文主要是介绍BZOJ 4033. [HAOI2015]树上染色（树形DP，边贡献），希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！

Description
有一棵点数为N的树，树边有边权。给你一个在0~N之内的正整数K，你要在这棵树中选择K个点，将其染成黑色，并
将其他的N-K个点染成白色。将所有点染色后，你会获得黑点两两之间的距离加上白点两两之间距离的和的收益。
问收益最大值是多少。
Input
第一行两个整数N,K。
接下来N-1行每行三个正整数fr,to,dis，表示该树中存在一条长度为dis的边(fr,to)。
输入保证所有点之间是联通的。
N<=2000,0<=K<=N
Output
输出一个正整数，表示收益的最大值。
Sample Input
5 2
1 2 3
1 5 1
2 3 1
2 4 2
Sample Output
17
【样例解释】
将点1,2染黑就能获得最大收益。
Hint
2017.9.12新加数据一组 By GXZlegend

思路：
老套路题了，按边统计贡献。

定义 $d p [i] [j]$ 代表以 $i$ 为根节点子树选择了 $j$ 个黑点能得到边贡献的最大值。
那么转移就是 $d p [u] [j + q] = m a x (d p [u] [j + q], d p [u] [j] + d p [v] [q] + 白点对这条边贡献 + 黑点对这条边贡献)$ 。其中黑点对这条边贡献的算法为这个子树中的黑点数目乘以子树外黑点数目，白点同理。代码表示就是：

	for(int j = 0;j <= min(siz[v] + siz[x],k);j++) tmp[j] = 0;for(int j = min(siz[x],k);j >= 0;j--) { //父节点和之前子树选择的黑点个数for(int q = 0;q <= min(siz[v],k - j);q++) { //当前子节点的选择的黑点个数tmp[j + q] = max(tmp[j + q],dp[x][j] + dp[v][q] + 1ll * w * q * (k - q) + 1ll * w * (siz[v] - q) * (W - (siz[v] - q)));}}for(int j = 0;j <= min(siz[x] + siz[v],k);j++) dp[x][j] = tmp[j];siz[x] += siz[v];

转移看似是 $n*k^2$ 的，但实际不会超过 $n^2$ ，因为第一层循环不会超过当前节点 $x$ 和之前子树和 $s i z [x]$ ，第二层循环不会超过当前子树大小 $s i z [v]$ 。这实际等价于枚举任意两点的LCA，所以最坏复杂度 $n^2$ 。

#include <cstdio>
#include <cstring>
#include <algorithm>
#include <vector>
using namespace std;
typedef long long ll;
const int maxn = 2005;
const ll INF = 1e18;
int n,k,W;
ll dp[maxn][maxn],tmp[maxn];
int siz[maxn];
int head[maxn],nex[maxn * 2],to[maxn * 2],val[maxn * 2],tot;
void add(int x,int y,int z) {to[++tot] = y;nex[tot] = head[x];val[tot] = z;head[x] = tot;
}
void DP(int x,int fa) {siz[x] = 1;for(int i = head[x];i;i = nex[i]) {int v = to[i],w = val[i];if(v == fa) continue;DP(v,x);for(int j = 0;j <= min(siz[v] + siz[x],k);j++) tmp[j] = 0;for(int j = min(siz[x],k);j >= 0;j--) { //父节点和之前子树选择的黑点个数for(int q = 0;q <= min(siz[v],k - j);q++) { //当前子节点的选择的黑点个数tmp[j + q] = max(tmp[j + q],dp[x][j] + dp[v][q] + 1ll * w * q * (k - q) + 1ll * w * (siz[v] - q) * (W - (siz[v] - q)));}}for(int j = 0;j <= min(siz[x] + siz[v],k);j++) dp[x][j] = tmp[j];siz[x] += siz[v];}
}
int main() {scanf("%d%d",&n,&k);W = n - k;//白点数目for(int i = 1;i < n;i++) {int x,y,z;scanf("%d%d%d",&x,&y,&z);add(x,y,z);add(y,x,z);}DP(1,0);printf("%lld\n",dp[1][k]);return 0;
}