【树形背包】BZOJ4033 [HAOI2015]树上染色

题面在这里

​

树形背包第一题……

这题只要考虑子树到父节点的边对答案的贡献即可，即： \[ w\cdot (k(K-k)+(s_y-k)(n-K-(s_y-k))) \] 然后定义\(f_{i,j}\)表示子树i内有j个黑点，子树i内的边对答案的贡献

然后把黑点看成物品就是树形背包了

树形背包的转移方法就是把子树一个一个地合并进来

所以不能把所有子树答案先求出来，size也要一边求一边DP

​

示例程序：

#include<cstdio>
#include<algorithm>
using namespace std;
typedef long long ll;

const int maxn=2005,maxe=4005;
int n,K,s[maxn];
ll f[maxn][maxn];
int tot,son[maxe],nxt[maxe],lnk[maxn],w[maxe];
inline void add(int x,int y,int z){
	son[++tot]=y;nxt[tot]=lnk[x];lnk[x]=tot;w[tot]=z;
}
void dfs(int x,int fa){
	s[x]=1;
	for (int i=lnk[x];i;i=nxt[i])if (son[i]!=fa){
		int y=son[i]; dfs(y,x);
		for (int j=min(K,s[x]);j>=0;j--)
		 for (int k=min(K,s[y]);k>=0;k--) if (j+k<=K)
		  f[x][j+k]=max(f[x][j+k],f[x][j]+f[y][k]+(ll)w[i]*(k*(K-k)+(s[y]-k)*(n-K-(s[y]-k))));
		s[x]+=s[y];
	}
}
int main(){
	scanf("%d%d",&n,&K);
	for (int i=1,x,y,z;i<n;i++) scanf("%d%d%d",&x,&y,&z),add(x,y,z),add(y,x,z);
	dfs(1,1);
	printf("%lld",f[1][K]);
	return 0;
}