当前位置：首页 > ds >正文

34.树形 DP

ds 2025/7/5 0:58:10

一、算法内容

树形动态规划，就是在树这一特殊的结构上维护、更新状态的最优解。

通常，我们从根结点出发，向子结点作深度优先搜索，并由其子结点的最优解合并得到该结点的最优解。因此在大多数时候我们都需要借助递归和回溯来帮助我们完成动态规划的过程。

比如，我们现在需要计算子树 $u$ 的大小 $s i ze [u]$ ，首先遍历其所有子结点 $c hi l d s [u]$ ，再由子结点的 $s i ze$ 累加得到，即：
$size[u]=\sum size[v],v\in children(u).$
有些问题，我们还需再次从根结点出发，向子结点作深度优先搜索。对于树上的每个结点（除根结点以外），由父结点的信息（父结点合并后的信息，除去该孩子的信息，就是其余孩子的信息）更新该结点的信息。

二、实例分析

1. P1352 没有上司的舞会

（1）题目大意

这里有一棵总共有 $n$ 个结点的树，根节点已经确定，每一个结点都有一个权值。现在要求选择树上的一些结点，使得它们的权值和最大，并且满足所选择的所有结点之间都没有父子关系。

（2）题目分析

很显然，每个结点只有选择和不选择两种情况，我们可以将这两种状态分别表示为 $1$ 和 $0$ 。
不难发现一个结点选择与否的结果只会影响到自己上一层的选择情况，这就满足了无后效性。
设 $u$ 是当前结点， $v$ 代表它的子结点。 $d p [u] [0]$ 表示不选择 $u$ 的最大权重， $d p [u] [1]$ 表示选择 $u$ 的最大权重。根据所选择结点没有父子关系这一条件，很容易得出状态转移方程：
$\begin{aligned} dp[u][0] &= dp[u][0]+\sum\max(dp[v][0], dp[v][1]),\\ dp[u][1] &= dp[u][1]+\sum\max(dp[v][0]), \end{aligned}$
$v$ 遍历 $u$ 的所有子结点。
可以观察到题目是满足最优子结构的。
时间复杂度为 $O (n)$

（3）核心代码

void dfs(ll u)
{for(ll i = p[u]; i != -1; i = e[i].next){ll v = e[i].v;dfs(v);dp[u][0] += max(dp[v][0], dp[v][1]);dp[u][1] += dp[v][0]; }
}

2. 二叉苹果树

（1）题目大意

这里有一棵苹果树，它共有 $N$ 个结点，编号为 $\sim N$ ，树根编号一定是 $1$ 。我们用一根树枝两端连接的结点的编号来描述一根树枝的位置。现在这颗树枝条太多了，需要剪枝。但是一些树枝上长有苹果。给定需要保留的树枝数量，求出最多能留住多少苹果。

（2）题目分析

首先我们需要尊重一下物理原理，当某条边被保留下来时，从根节点到这条边的路径上的所有边也都必须保留。
不难发现对于每棵子树的情况来说，我们只需要记录以它为根且保留 $j$ 条边能获得的最大苹果数目即可，至于具体它如何保留的并不重要。这就满足了 $d p$ 的条件。
特别注意，对于父节点 $u$ 来说，如果要保留子结点 $v$ 的这颗子树，那么 $(u, v)$ 这条边也是一定要保留的。
如此一来我们其实就把该问题转化为了一个 $01$ 背包问题，背包容量是父节点 $u$ 总共要保留的边数 $j$ ，物品就是子节点 $v$ 要保留的边数 $k$ ，物品的价值就是这棵子树对应的苹果数量以及这条边的苹果数量
设 $d p [u] [j]$ 表示以 $u$ 为根的子树上保留 $j$ 条边时能获得的苹果数目最大值，那么状态转移方程可以表示为：
$dp[u][j]=\max(dp[u][j],dp[u][j-k-1]+dp[v][k]+e[i].w)$
时间复杂度为 $O(n^3)$

（3）核心代码

void dfs(ll u, ll pre)
{for(ll i = p[u]; i != -1 ; i = e[i].next){ll v = e[i].v;if(v != pre){dfs(v, u);for(ll j = m; j >= 1; j--)for(ll k = 0; k <= j - 1; k++)dp[u][j] = max(dp[u][j], dp[u][j - k - 1] + dp[v][k] + e[i].w);}}
}