树形 DP,是一种 DP (废话),专门用于树上的 DP。
这类 DP 因为其板子好记,标记显眼而十分易懂。
而且树形 DP 长得就不像 DP,更像暴力搜索。
当然 DP 肯定也有很大思维量的,但是像树形 DP 代码确实挺好打。
例题:P1352 没有上司的舞会
题目实际上就是给出一棵有 \(n\) 个点的树,选出一些点,使得这些点两两不相邻,求最大点权和。
这就是树形 DP 的板子题。
首先先把树存下来。
前言里面说过:树形 DP 更像一种暴力搜索,于是我们需要对这棵树做一遍 dfs,边 dfs 边 DP。
考虑到树形 DP 是一种 DP (难道不是吗),所以我们仍然需要 DP 的基本套路:设状态,推转移方程,推初值,求答案。
以下的所有讨论都假设已经确定树的形态以及根。
设 \(f_{k,0/1}\) 表示节点 \(k\) 以及其子树选出点的最大权值和。\(0\) 表示节点 \(k\) 不放,\(1\) 表示节点 \(k\) 放。
那么作为树形 DP,很重要的一点就是:父节点的 \(f\) 的计算是与子节点有关系的。
因此对于这道题,我们的状态转移方程如下:
\[f_{k,0}=\max\{f_{u,0},f_{u,1} | u \in V\} \]\[f_{k,1}=r_k+\max\{f_{u,0} | u \in V\} \]其中 \(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...); /*转移*/ } }
练习题传送门:DP算法总结&专题训练2(树形 DP)