树上分组背包问题

  第一次碰到这种树上的背包问题，记录一下，后续会慢慢补充。

题目链接 《P1273 有线电视网》

关键：
  把每个结点看成一个背包，体积就是该结点为根的子树中的用户总数量。并且以该结点为根的子树中的用户选择数量作为不同组别（每一种数量看成是组内的一种物品），进行分组背包求解。

完整的状态定义为三维：

  $f[u][i][j]:$ 表示以 $u$ 为根的子树，且只选其中的 $i$ 个用户，所选用户数量不超过 $j$ 的方案集合的最大价值。

状态转移方程：

  $f[u][i][j] = max(f[u][i - 1][j - k] + f[son][size(son)][k] - cost[u][son])$。

• son表示选择的某个子结点.
• k表示分给son的体积。

  三维会 $MLE$，因此可以根据转移方程优化掉第一维，由于树形$DP$采用 $dfs$ 形式，是自底向上的，所以在计算以 $u$ 为根结点时，以 $son$ 为根的情况已经算完了，所以 $f[son][k]$ 这一项不受影响。而前一项需要类比 $01$ 背包，对体积从大到小枚举。

  因此二维状态表示 $f[u][j]$ 对应的转移方程如下：

  $f[u][j] = max(f[u][j - k] + f[son][k] - cost[u][son])$

答案： 统计一遍，$f[1][j] \ge 0$ 时最大的 $j$ 就是答案。

注意： $f$ 的初始化

AC代码：

#include <bits/stdc++.h>
using namespace std;

const int N = 3010;
int h[N], e[N], w[N], ne[N], idx;
int val[N], f[N][N];  //f[i][j]: 以i为根结点，选择用户数量不超过j的方案的最大价值，答案就是f[1][j] > 0中的Max(j) 
int n, m;
int ans;

void add(int a, int b, int c){
	e[idx] = b, w[idx] = c, ne[idx] = h[a], h[a] = idx++;
}

int dfs(int u, int p){
	if(u > n - m){  //已经到达用户终端 
		f[u][1] = val[u];
		return 1;
	}
	int s = 0;
	for(int i = h[u]; ~i; i = ne[i]){
		int son = e[i];
		if(son == p) continue;
		int t = dfs(son, u);
		s += t;
		for(int j = m; j >= 0; j--){
			//分组选取
			for(int k = 0; k <= t; k++){
				if(j - k >= 0) f[u][j] = max(f[u][j], f[u][j - k] + f[son][k] - w[i]);
			} 
		}
	}
	return s;
}

void solve(){
	scanf("%d%d", &n, &m); 
	memset(h, -1, sizeof h);
	memset(f, -0x3f, sizeof f);
	for(int i = 1; i <= n - m; i++){
		int k;
		scanf("%d", &k);
		for(int j = 0; j < k; j++){
			int x, c;
			scanf("%d%d", &x, &c);
			add(i, x, c);
		}
	}
	for(int i = n - m + 1; i <= n; i++) scanf("%d", &val[i]);
	for(int i = 1; i <= n; i++) f[i][0] = 0;
	dfs(1, -1);

	for(int j = m; j >= 0; j--){
		if(f[1][j] >= 0){
			ans = j;
			break;
		}
	}
	printf("%d\n", ans);
}

int main(){
	int T = 1;
//	scanf("%d", &T);
	while(T -- ){
		solve();
	}
	return 0;
}