树形DP：在“树”的数据结构上做动态规划，通过有限次地遍历树，记录相关信息，以求解问题。
树形动态规划是建立在树上的，树中的父子关系天然就是个递归（子问题）结构，所以也相应的有二个方向：
1. 叶子 → 根：即根的子节点传递有用的信息给根，之后由根得出最优解的过程。
2. 根 → 叶子：即需要取所有点作为一次根节点进行求值，此时父亲得到了整棵树的信息，只需将其中这个儿子的DP值的影响去除，然后再转移给这个儿子，这样就能达到根 → 叶子的顺序。
树形DP一般按照后序遍历的顺序，即处理完儿子再处理当前节点，这符合树的子结构的性质。
树形dp的主要实现形式是dfs (记忆化搜索)，在dfs中dp，主要的实现形式是dp[i][j][0/1]，i 是以 i 为根的子树，j 是表示在以 i 为根的子树中选择 j 个子节点，0 表示这个节点不选，1 表示选择这个节点。有的时候j或0/1这一维可以压掉。基本的转移方程如：
时间复杂度：树形DP复杂度基本上是 O(n) ；若有附加维m，则是 O(n*m) 。