通常#xff0c;我们从根结点出发#xff0c;向子结点作深度优先搜索#xff0c;并由其子结点的最优解合并得到该结点的最优解。

因此在大多数时候我们都需要借助递归和回溯来帮助…一、算法内容

通常我们从根结点出发向子结点作深度优先搜索并由其子结点的最优解合并得到该结点的最优解。

因此在大多数时候我们都需要借助递归和回溯来帮助我们完成动态规划的过程。

比如我们现在需要计算子树

有些问题我们还需再次从根结点出发向子结点作深度优先搜索。

对于树上的每个结点除根结点以外由父结点的信息父结点合并后的信息除去该孩子的信息就是其余孩子的信息更新该结点的信息。

二、实例分析

个结点的树根节点已经确定每一个结点都有一个权值。

现在要求选择树上的一些结点使得它们的权值和最大并且满足所选择的所有结点之间都没有父子关系。

2题目分析

很显然每个结点只有选择和不选择两种情况我们可以将这两种状态分别表示为

不难发现一个结点选择与否的结果只会影响到自己上一层的选择情况这就满足了无后效性。

dp[u][0]

的最大权重。

根据所选择结点没有父子关系这一条件很容易得出状态转移方程

max

dp[u][0]dp[u][1]​dp[u][0]∑max(dp[v][0],dp[v][1]),dp[u][1]∑max(dp[v][0]),​

时间复杂度为

1。

我们用一根树枝两端连接的结点的编号来描述一根树枝的位置。

现在这颗树枝条太多了需要剪枝。

但是一些树枝上长有苹果。

给定需要保留的树枝数量求出最多能留住多少苹果。

2题目分析

首先我们需要尊重一下物理原理当某条边被保留下来时从根节点到这条边的路径上的所有边也都必须保留。

条边能获得的最大苹果数目即可至于具体它如何保留的并不重要。

这就满足了

特别注意对于父节点

dp[u][j]\max(dp[u][j],dp[u][j-k-1]dp[v][k]e[i].w)

dp[u][j]max(dp[u][j],dp[u][j−k−1]dp[v][k]e[i].w)

时间复杂度为