15 树上背包

适用于树形 $dp$ 的情况，父节点的情况依赖于子节点的取舍，往往采用 $DFS(后序遍历）$ 进行动态转移

也有可能反过来，总而言之是具有一定依赖性的

树形背包

//u为现在的根节点，cnt为当前选择了几个节点
void dfs(int u, int cnt){
	for(auto v: G[u]){//遍历所有子节点
	
		//将u的价值先传递给j,为什么cnt-1是因为要给 u, v 留出一个位置 , 这啥时候写的神秘笔记
		rep(j, 0, cnt-1){
			dp[v.first][j] = dp[u][j] + v.second;
		}
		
		//处理
		dfs(v.first, cnt - 1);
		rep(j, 1, t){
			dp[u][j] = max(dp[u][j], dp[v.first][j-1]);
		}
	
	}
}

例题

二叉苹果树

题意

略

题解

$dfs$ 下保留保留 $u$ 点至少需要 $cnt$ 纸条开始遍历，向上向下传 $dp$

void dfs(int u, int f, int cnt){ 
	if(cnt > k) return; //想要到 u 点必须至少保留 cnt 条边
	for(auto x : G[u]){
		int v = x.first;
		int w = x.second;
		if(v == f) continue;
		
		rep(i, cnt + 1, k){  
			dp[v][i] = dp[u][i - 1] + w; 
		}
 
		dfs(v, u, cnt + 1);
 
		rep(i, cnt + 1, k){
			dp[u][i] = max(dp[u][i], dp[v][i]);
		}
	}
	return;
}

偷天换日

题意
现在有一个博物馆，每个走廊的尽头不是一个有藏品的房间，就是两条走廊。
房间内有若干副画，价值不同，偷画和经过走廊都需要时间。
警察还有 $n$ 就将到达门口，小偷如果第 $n$ 秒的时候还在博物馆，他就要被抓了，请问小偷在不被抓的情况下，最多偷几幅画

输入按照深度优先给出，房间和走廊的数量总共不超过 300
每组数据给出 $t,x$ ，$x$ 代表藏品数量，如果是 0 说明是走廊，如果不是，那么后面跟的 $x$ 组 $w,t$ 代表画的价值和偷画的时间 ， $x$ 不超过 30

题解
易错点在于需要使用 $dfs$ 去读取数据，直接看代码

struct node{
	int to, ww, tt;
};
int n;
vector<node> G[N];
vii dp(N, vi(610)); 
 
int p = 0;
void dfs1(int u){   //dfs 读取数据部分
	int t, x; cin >> t >> x;
	p ++;
	G[u].push_back({p, 0, 2 * t});
	int v = p;
	if(x == 0){
		dfs1(v);
		dfs1(v);
	}else{
		rep(i, 1, x){
			int w, t; cin >> w >> t;
			p ++;
			G[v].push_back({p, w, t});	
		}
	}
	return;
}
 
void dfs2(int u, int time){  //树形背包部分
	//cout << u << " " << time << endl;
	if(time >= n) return;
	for(auto tmp : G[u]){
		int v = tmp.to;
		//cout << u << " " << v << " " << tmp.ww<< endl;
		//cout << "? " << u << " " << v << endl;
		int t = tmp.tt;
		int w = tmp.ww;
 
		rep(i, time + t, n){
			dp[v][i] = dp[u][i - t] + w; 
		}
 
		dfs2(v, time + t);
 
		rep(i, time + t, n){
			dp[u][i] = max(dp[u][i], dp[v][i]);
		}
	}
	return;
}
 
void solve(){
	cin >> n; 
 
	dfs1(0);
	dfs2(0, 0);
	int res = 0;
	rep(i, 0, n - 1){
		res = max(res, dp[0][i]);
	}
	cout << res << endl;
	return;
}