• 1. 前言
• 2. 详解
• 3. 练习题

1. 前言

树形 DP，是一种 DP （废话），专门用于树上的 DP。

这类 DP 因为其板子好记，标记显眼而十分易懂。

而且树形 DP 长得就不像 DP，更像暴力搜索。

当然 DP 肯定也有很大思维量的，但是像树形 DP 代码确实挺好打。

2. 详解

例题：P1352 没有上司的舞会

题目实际上就是给出一棵有 \(n\) 个点的树，选出一些点，使得这些点两两不相邻，求最大点权和。

这就是树形 DP 的板子题。

首先先把树存下来。

前言里面说过：树形 DP 更像一种暴力搜索，于是我们需要对这棵树做一遍 dfs，边 dfs 边 DP。

考虑到树形 DP 是一种 DP （难道不是吗），所以我们仍然需要 DP 的基本套路：设状态，推转移方程，推初值，求答案。

以下的所有讨论都假设已经确定树的形态以及根。

设 \(f_{k,0/1}\) 表示节点 \(k\) 以及其子树选出点的最大权值和。\(0\) 表示节点 \(k\) 不放，\(1\) 表示节点 \(k\) 放。

那么作为树形 DP，很重要的一点就是：父节点的 \(f\) 的计算是与子节点有关系的。

因此对于这道题，我们的状态转移方程如下：

其中 \(V\) 为 \(k\) 的儿子组成的集合。

如果这个点不选，那么儿子可选可不选；但是如果选了，那么儿子不能选。

注意：选出的点集 \(U=\varnothing\) 也是可以的，因此可能答案为 \(0\)。

最后的答案为 \(f_{root,0/1}\) 中的最大值。

代码：

#include <bits/stdc++.h>
#define Max(a, b) ((a > b) ? a : b)
using namespace std;

typedef long long LL;
const int MAXN = 6e3 + 10;
int n, r[MAXN], f[MAXN][2], root;
vector <int> Next[MAXN];
bool book[MAXN];

int read()
{
	int sum = 0, fh = 1; char ch = getchar();
	for (; ch < '0' || ch > '9'; ch = getchar()) fh -= (ch == '-') << 1;
	for (; ch >= '0' && ch <= '9'; ch = getchar()) sum = (sum << 3) + (sum << 1) + (ch ^ 48);
	return sum * fh;
}

void dfs(int now, int fa)
{
	f[now][0] = 0, f[now][1] = r[now];
	for (int i = 0; i < Next[now].size(); ++i)
	{
		int u = Next[now][i];
		if (u == fa) continue;
		dfs(u, now);
		f[now][0] = Max(f[now][0], Max(f[now][0] + f[u][0], f[now][0] + f[u][1]));
		f[now][1] = Max(f[now][1], f[now][1] + f[u][0]);
	}
}

int main()
{
	n = read();
	for (int i = 1; i <= n; ++i) r[i] = read();
	for (int i = 1; i < n; ++i)
	{
		int x = read(), y = read(); book[x] = 1;
		Next[y].push_back(x); Next[x].push_back(y);
	}
	for (int i = 1; i <= n; ++i)
		if (!book[i]) {root = i; break;}
	dfs(root, root);
	printf("%d\n", Max(f[root][0], f[root][1]));
	return 0;
}

这里提供一种树形 DP 的板子，但是不能保证这个板子能够通过所有题目。

int f[...];

void dfs(int now, int fa...)
{
	/*设置初值*/
	for (/*遍历儿子*/)
	{
		int u = /*儿子*/;
		if (u == fa) continue;//注意不能返回父亲节点
		dfs(u, now...);
		/*转移*/
	}
}

3. 练习题

练习题传送门：DP算法总结&专题训练2（树形 DP）