概述

树形dp其实相对更加套路 状态转移方式基本上是确定的，无外乎就是子到父，父到子转移
不过状态的设计还是难的，有些时候有四五个状态也正常
树上天然的可以使用dfs，所以dfs也是常用的

P2015 二叉苹果树【树形背包】

入门题，
有dp数组：dp[i][j]：以i为根节点的树，保留j根枝条的最大值
我做得可能会智障一点，我会做一个分类，
选一颗子树和选两棵子树
选一颗子树：
dp[x][i] = max3(dp[x][i], dp[son[0]][i-1] + w[0], dp[son[1]][i-1] + w[1]);
选两棵子树：
dp[x][i] = max(dp[x][i], dp[son[0]][j] + dp[son[1]][i - 2 - j] + w[0] + w[1]);(2<=i<=Q&&0<=j<=i-2)
这种题还是更适合链式向前星，方便快捷
AC代码：

//P2015
#include<iostream>
#include<vector>
#include<algorithm>
#include<cstring>
using namespace std;
#define MAX 105
#define max3(a,b,c) (a>b?(a>c?a:c):(b>c?b:c))
#define max4(a,b,c,d)  (a>b?a:b)>(c>d?c:d)?(a>b?a:b):(c>d?c:d)
struct  Edge
{
	int to; int next; int w;
}edges[MAX*2];
int cnt,  head[MAX * 2], N, Q;
int dp[MAX][MAX];//第i个留j条
void init() {
	memset(head, -1, sizeof(head));
	cnt = 0;
}
void add(int from, int to, int w) {
	edges[cnt] = { to,head[from],w };
	head[from] = cnt++;
}

void dfs(int x,int fa) {

	vector<int>son;
	vector<int>w;
	for (int i = head[x]; ~i; i = edges[i].next) {
		int to = edges[i].to;
		if (to == fa)continue;
		son.push_back(to);
		w.push_back(edges[i].w);
	}
	if (son.empty())return;
	dfs(son[0], x), dfs(son[1], x);
	if (x == 3)
		int a = 1;
	//只选一个儿子
	for (int i = 1; i <= Q; i++) 
		dp[x][i] = max3(dp[x][i], dp[son[0]][i-1] + w[0], dp[son[1]][i-1] + w[1]);
	//两个儿子都要选
	for (int i = 2; i <= Q; i++) {
		for (int j = 0; j <= i - 2; j++)
			dp[x][i] = max(dp[x][i], dp[son[0]][j] + dp[son[1]][i - 2 - j] + w[0] + w[1]);
	}
}

int main() {
	std::ios::sync_with_stdio(false);
	cin >> N >> Q;
	init();
	for (int i = 0; i < N - 1; i++) {
		int a, b, c;
		cin >> a >> b >> c;
		add(a, b, c);
		add(b, a, c);
	}
	dfs(1,0);
	cout << dp[1][Q];
}

树形DP

原文：https://www.cnblogs.com/zhpisnotphz/p/12856243.html