树形DP
树的特征
- 有N个点，N-1条边的无向图，任意两顶点间可达
- 无向图中任意两个点间有且仅有一条路
- 一个点至多有一个前趋，但可以有多个后继
- 无向图中没有环
树形DP
树可以描述比较复杂的关系，对选手分析问题的能力有较高的要求，在寻找最优子结构、组织状态时往往需要创造性思维，而且树型动态规划对数学要求不高，不涉及单调性优化等方面，所以竞赛中往往将它作为侧重考察选手分析思考能力的题型出现。 大多数动规都是在一维二维这种规则背景下，解决的问题比较局限 树作为一种特殊的图，可以描述比较复杂的关系，再加上树的递归定义，是一种非常合适动规的框架，树型动态规划就成为动规中很特殊的一种类型。
最重要的是树有时候保证了没有后效性
分析
问题：给一棵树，要求以最少的代价（或最大收益）完成给定的操作 树型DP是建立在树上的，有两个方向：
- 根→叶：这种动态规划在实际的问题中运用的不多
- 叶→根：即根的子节点传递有用的信息给根，然后根得出最优解的过程，这类的题目比较的多。
