树形DP

　　通过上一节的学习，应该对动态规划在树形结构上的实现方式有了初步的认识。给定一棵有N个节点的树（通常是无根树，也就是有N - 1条无向边），我们可以任选一个结点为根节点，从而定义出每个节点的深度和每棵子树的根。在树上设计动态规划算法时，一般就以节点从深到浅（子树从小到大）的顺序作为DP的“阶段”。DP的状态表示中，第一维通常是节点编号（代表以该节点为根的子树）。大多数时候，我们采用递归的方式实现树形动态规划。对于每个节点 x，先递归在它的每个子节点上进行DP，在回溯时，从子节点向节点 x进行状态转移。

1、基本概念

　　树形DP称为树形动态规划，顾名思义，就是在“树”的结构上做动态规划，通过有限次地遍历树，记录相关信息，以求解问题。通常，动态规划都是线性的或者是建立在图上的，线性动态规划的顺序有两种方向：即向前和向后，相应的状态转移方程有两种，即顺推与逆推，而树形动态规划是建立在树上的，树中的父子关系天然就是个递归（子问题）结构，所以也相应的有两个方向。

1. 叶 -> 根，即根的子节点传递有用的信息给根，之后由根得出最优解的过程。这种方式DP的题目应用比较多。
2. 根 -> 叶，即需要取所有点作为一次根节点进行求值，此时父节点得到了整棵树的信息，只需要去除这个儿子的PD值的影响，然后再转移给这个儿子，这样就能达到根 -> 叶的顺序。

　　动态规划的顺序：一般按照后序遍历的顺序，即处理完儿子再处理当前结点，才符合树的子节点的性质。

　　实现方式：树形DP是通过记忆化搜索实现的，因此采用的是递归方式。

　　时间复杂度：树形动态规划的时间复杂度基本上是O(n)；若有附加维m，则是O(n * m)。

树形DP

原文：https://www.cnblogs.com/longxue1991/p/12826627.html