树形DP
给出一棵树，要求以最少代价（或最大收益）完成给定的操作。
基本操作
- 树的遍历，用DFS从根节点开始进行记忆化搜索
- 从树最深处开始往回进行DP，用子节点dp值来更新父节点dp值
复杂度分析：遍历每个节点，总复杂度为\(O(n)\)
例题
某大学有 \(n\) 个职员，编号为 \(1\ldots n\)。
他们之间有从属关系，也就是说他们的关系就像一棵以校长为根的树，父结点就是子结点的直接上司。
现在有个周年庆宴会，宴会每邀请来一个职员都会增加一定的快乐指数 \(r_i\)，但是呢，如果某个职员的直接上司来参加舞会了，那么这个职员就无论如何也不肯来参加舞会了。
所以，请你编程计算，邀请哪些职员可以使快乐指数最大，求最大的快乐指数。
题目分析：
根据\(DP\)的解题思路，定义状态：dp[i][0]表示不选择当前节点的最优解，dp[i][1]表示参加当前节点的最优解。
状态转移方程有两种情况(设\(u\)为父节点，\(v\)为子节点)：
1.不选择当前节点，那么它的子节点可选可不选，取其中的最大值，即
dp[u][0] += max(dp[v][0], dp[v][1])
2.选择当前节点，那么它的子节点不可选，即
dp[u][0] += (dp[v][0])
实现代码：
#include <bits/stdc++.h>
using namespace std;
const int N = 6005;
int val[N], dp[N][2], father[N];
vector<int> G[N];
void addedge(int from, int to)
{
G[from].push_back(to); // 用邻接表建树
father[to] = from; // 父子关系
}
void dfs(int u)
{
dp[u][0] = 0; // 赋初值：不参加宴会
dp[u][1] = val[u]; // 赋初值：参加宴会
for (int i = 0; i < G[u].size(); i++)
{ // 遍历u的邻居v。逐一处理这个父结点的每个子结点
int v = G[u][i];
dfs(v); // 深搜子结点
dp[u][1] += dp[v][0]; // 父结点选择，子结点不选
dp[u][0] += max(dp[v][0], dp[v][1]); // 父结点不选，子结点可选可不选
}
}
int main()
{
int n;
scanf("%d", &n);
for (int i = 1; i <= n; i++)
scanf("%d", &val[i]); // 输入快乐指数
for (int i = 1; i < n; i++)
{
int u, v;
scanf("%d%d", &u, &v);
addedge(v, u);
}
int t = 1;
while (father[t])
t = father[t]; // 查找树的根结点
dfs(t); // 从根结点开始，用dfs遍历整棵树
printf("%d\n", max(dp[t][0], dp[t][1]));
return 0;
}
模板
由例题，可以总结出来树形dp核心部分的模板：
void dfs(int u)
{
dp[u][...] = ...; //初始化
for(int i=0; i < edge[u].size(); i++) //遍历处理u的子节点v
{
int v = G[u][i];
dfs(v); //深搜子结点
dp[u][...] = ...; //状态转移方程
}
}
树上背包
树上的背包问题，简单来说就是背包问题与树形 DP 的结合。
例题
某收费有线电视网计划转播一场重要的足球比赛。他们的转播网和用户终端构成一棵树状结构，这棵树的根结点位于足球比赛的现场，树叶为各个用户终端，其他中转站为该树的内部节点。
从转播站到转播站以及从转播站到所有用户终端的信号传输费用都是已知的，一场转播的总费用等于传输信号的费用总和。
现在每个用户都准备了一笔费用想观看这场精彩的足球比赛，有线电视网有权决定给哪些用户提供信号而不给哪些用户提供信号。
写一个程序找出一个方案使得有线电视网在不亏本的情况下使观看转播的用户尽可能多。
题目分析:
我们设 \(dp(u,i,j)\) 表示以 \(u\) 号点为根的子树中，已经遍历了 \(u\) 号点的前 \(i\) 棵子树，选了 \(j\) 个用户的最大收益。
转移的过程结合了树形 DP 和 背包 DP 的特点，我们枚举 \(u\) 点的每个子结点 \(v\)，同时枚举以 \(v\) 为根的子树选了几个用户，将子树的结果合并到 \(u\) 上。
记点 \(x\) 的儿子个数为 \(s_x\)，以 \(x\) 为根的子树所有的用户数量 \(\textit{siz_x}\) ，可以写出下面的状态转移方程：
注意上面状态转移方程中的几个限制条件，这些限制条件确保了一些无意义的状态不会被访问到。
\(dp\) 的第二维可以很轻松地用滚动数组的方式省略掉，注意这时需要倒序枚举 \(j\) 的值。
则 \(dp\) 循环实现：
for (int i = 0; i < edge[u].size(); i++) // 把u的每个子树看作一个组
{
...
for (int j = sum[u]; j >= 0; j--) // 把u下的用户总数总数看成背包容量
for (int k = 1; k <= sum[v]; k++) // 用k遍历每个子树的每个用户
dp[u][j] = max(dp[u][j], dp[u][j - k] + dp[v][k] - w);
}
实现代码：
#include <cstdio>
#include <iostream>
#include <algorithm>
#include <vector>
#include <cstring>
using namespace std;
const int N = 3e3 + 5;
struct node
{
int v, w;
node(int x = 0, int y = 0) : v(x), w(y) {}
};
vector<node> edge[N];
int n, m, val[N], sum[N];
int dp[N][N];
void dfs(int u)
{
if (val[u])
{
dp[u][1] = val[u];
sum[u] = 1;
return;
}
for (int i = 0; i < edge[u].size(); i++)
{
int v = edge[u][i].v, w = edge[u][i].w;
dfs(v);
sum[u] += sum[v];
for (int j = sum[u]; j > 0; j--)
for (int k = 1; k <= sum[v]; k++)
dp[u][j] = max(dp[u][j], dp[u][j - k] + dp[v][k] - w);
}
return;
}
int main()
{
memset(dp, -0x3f3f3f3f, sizeof dp); //初始化一个极大负值，因为dp可能为负
scanf("%d %d", &n, &m);
for (int i = 1; i <= n - m; i++)
{
int k;
scanf("%d", &k);
while (k--)
{
int a, c;
scanf("%d %d", &a, &c);
edge[i].push_back(node(a, c));
}
}
for (int i = 1; i <= m; i++)
scanf("%d", &val[n - m + i]);
for (int i = 1; i <= n; i++)
dp[i][0] = 0; //选0个用户的花费是0
dfs(1);
for (int i = m; i >= 1; i--)
if (dp[1][i] >= 0)
{
printf("%d", i);
break;
}
return 0;
}
题单
| 序号 | 题号 | 标题 | 题型 | 题解 |
|------|------------|--------------------------|---------------- | -------------|:-----|
| 1 ||||? |
| 2 || ||? |
| 3 | | | |? |
| 4 || | |? |