树形 DP，即在树上进行的 DP。由于树固有的递归性质，树形 DP 一般都是递归进行的。
基础以下面这道题为例，介绍一下树形 DP 的一般过程。
例题 洛谷 P1352 没有上司的舞会
题目描述某大学有 $n$ 个职员，编号为 $1 \sim N$。他们之间有从属关系，也就是说他们的关系就像一棵以校长为根的树，父结点就是子结点的直接上司。现在有个周年庆宴会，宴会每邀请来一个职员都会增加一定的快乐指数 $a_i$，但是呢，如果某个职员的上司来参加舞会了，那么这个职员就无论如何也不肯来参加舞会了。所以，请你编程计算，邀请哪些职员可以使快乐指数最大，求最大的快乐指数。
我们可以定义 \(f(i,0/1)\) 代表以 \(i\) 为根的子树的最优解（第二维的值为 0 代表 \(i\) 不参加舞会的情况，1 代表 \(i\) 参加舞会的情况）。
显然，我们可以推出下面两个状态转移方程（其中下面的 \(x\) 都是 \(i\) 的儿子）：
\(f(i,0) = \sum\max \{f(x,1),f(x,0)\}\)（上司不参加舞会时，下属可以参加，也可以不参加）
\(f(i,1) = \sum{f(x,0)} + a_i\)（上司参加舞会时，下属都不会参加）
我们可以通过 DFS，在返回上一层时更新当前结点的最优解。
代码const int N = 1e4 + 10; vector tr[N]; int f[N][2], v[N], Happy[N], n; void dfs(int u) { f[u][0] = 0; f[u][1] = Happy[u]; for (auto v : tr[u]) { dfs(v); f[u][0] += max(f[v][0], f[v][1]); f[u][1] += f[v][0]; } } int main() { cin.tie(nullptr)->sync_with_stdio(false); cin >> n; for (int i = 1; i <= n; ++i) cin >> Happy[i]; for (int i = 1, x, y; i < n; ++i) { cin >> x >> y; v[x] = 1;// x has a father tr[y].push_back(x); } int root; for (int i = 1; i <= n; ++i) if (!v[i]) {root = i; break;} dfs(root); cout << max(f[root][0], f[root][1]) << "\n"; }相关练习
HDU 2196 Computer
POJ 1463 Strategic game
POI2014 FAR-FarmCraft
树上背包树上的背包问题，简单来说就是背包问题与树形 DP 的结合。
例题 洛谷 P2014 CTSC1997 选课
题目描述现在有 $n$ 门课程，第 $i$ 门课程的学分为 $a_i$，每门课程有零门或一门先修课，有先修课的课程需要先学完其先修课，才能学习该课程。
一位学生要学习 $m$ 门课程，求其能获得的最多学分数。
$n,m \le 300$
每门课最多只有一门先修课的特点，与有根树中一个点最多只有一个父亲结点的特点类似。
因此可以想到根据这一性质建树，从而所有课程组成了一个森林的结构。为了方便起见，我们可以新增一门 \(0\) 学分的课程（设这个课程的编号为 \(0\)），作为所有无先修课课程的先修课，这样我们就将森林变成了一棵以 \(0\) 号课程为根的树。
我们设 \(f(u,i,j)\) 表示以 \(u\) 号点为根的子树中，已经遍历了 \(u\) 号点的前 \(i\) 棵子树，选了 \(j\) 门课程的最大学分。
转移的过程结合了树形 DP 和背包 DP 的特点，我们枚举 \(u\) 点的每个子结点 \(v\)，同时枚举以 \(v\) 为根的子树选了几门课程，将子树的结果合并到 \(u\) 上。
记点 \(x\) 的儿子个数为 \(s_x\)，以 \(x\) 为根的子树大小为 \(siz_x\)，很容易写出下面的转移方程：
\[f(u,i,j)=\max_{v,k \leq j,k \leq siz_v} f(u,i-1,j-k)+f(v,s_v,k) \]