参考书籍：
《信息学奥赛一本通提高版》
《算法竞赛进阶指南》
《算法竞赛入门经典（第2版）》
参考诸多博客汇总：
https://blog.csdn.net/txl199106/article/details/45373507
http://www.cnblogs.com/mhpp/p/6628548.html
https://blog.csdn.net/nan81962325/article/details/79837073
https://blog.csdn.net/qq_41444888/article/details/81503425
【定义】
顾名思义，树型动态规划就是在“树”的数据结构上的动态规划，平时作的动态规划都是线性的或者是建立在图上的，线性的动态规划有二种方向既向前和向后，相应的线性的动态规划有二种方法既顺推与逆推，而树型动态规划是建立在树上的，所以也相应的有二个方向：
1、叶－>根：在回溯的时候从叶子节点往上更新信息
2、根 - >叶：往往是在从叶往根dfs一遍之后（相当于预处理），再重新往下获取最后的答案。
不管是 从叶－>根 还是 从 根 - >叶，两者都是根据需要采用，没有好坏高低之分。
【算法应用】
给定一棵有N个节点的树(通常是无根树，也就是有N-1条无向边)，我们可以任选一个节点为根节点，从而定义出每个节点的深度和每棵子树的根。在树上设计动态规划算法时，一般就以节点从深到浅(子树从小到大)的顺序作为DP的“阶段”。DP的状态表示中，第一维通常是节点编号(代表以该节点为根的子树)。大多数时候，我们采用递归的方式实现树形动态规划。对于每个节点x，先递归在它的每个子节点上进行DP，在回溯时，从子节点向节点x进行状态转移。
【树的特点与性质】
1、 有n个点，n-1条边的无向图，任意两顶点间可达
2、 无向图中任意两个点间有且只有一条路
3、 一个点至多有一个前趋，但可以有多个后继
4、 无向图中没有环；
重点来了：
树形DP的这一特殊性：没有环，dfs是不会重复，而且具有明显而又严格的层数关系。利用这一特性，我们可以很清晰地根据题目写出一个在树（型结构）上的记忆化搜索的程序。而深搜的特点，就是“不撞南墙不回头”。下面例题具体解释。
所以，DP过程一般为：对于每个节点x，先递归在它的每个子节点上进行DP，在回溯时，从子节点向节点x进行状态转移。
【与线性DP不同】
计算顺序不同。
线性dp有两种方向，顺推与逆推；而树形dp也有两个方向。由根到叶的先根遍历，但不常用，一般我们采用由叶到根的后根遍历，即子节点将有用信息传给父节点，逐层上推，最终由根得出最优解。
计算方式不同.
线性的采用传统迭代，树形是用记忆化，用递归。
【过程】
1.判断是否是一道树规题：
即判断数据结构是否是一棵树，然后是否符合动态规划的要求。如果是，那么执行以下步骤，如果不是，那么换台。
2.建树：通过数据量和题目要求，选择合适的树的存储方式。
如果节点数小于5000，那么我们可以用邻接矩阵存储，如果更大可以用邻接表来存储(注意边要开到2*n，因为是双向的。这是血与泪的教训)。如果是二叉树或者是需要多叉转二叉，那么我们可以用两个一维数组brother[]，child[]来存储（这一点下面会仔细数的）。
3.树规方程：通过观察孩子和父亲之间的关系建立方程。我们通常认为，树形DP的写法有两种：
a.根到叶子: 不过这种动态规划在实际的问题中运用的不多。
b.叶子到根: 既根的子节点传递有用的信息给根，完后根得出最优解的过程。这类的习题比较的多。
注意：这两种写法一般情况下是不能相互转化的。但是有时可以同时使用具体往后看。
【难点】
1、和线性动态规划相比，树形DP往往是要利用递归的，所以对递归不熟悉的同学，是一道小小的障碍，说是小小的，因为要去理解也不难。
2、细节多，较为复杂的树形DP，从子树，从父亲，从兄弟……已经一些小的要处理的地方，脑子不清晰的时候做起来颇为恶心
3、状态表示和转移方程，也是真正难的地方。做到后面，树形DP的老套路都也就那么多，难的还是怎么能想出转移方程，状压DP、概率DP这些特别的DP应该说做到最后都是这样！
【经典例题】
入门题
1. 树的最大独立集
定义 ： 对于一颗n个节点的无根树，给出n-1条遍，选出尽量多的节点，使得任何两个节点均不相邻。输出一个最大独立集
思路 : 用d(i)表示以i为根结点的子树的最大独立集大小
对于结点i，只有两种选择，选或者不选，若选，则问题转化为求出i的孙子的d值之，若不选则转化为求i的儿子的d值之和,状态转移方程:d(i) = max(1 + gs[i], s[i])
经典例题：
2. 树的重心
定义 : 树的重心也叫树的质心。找到一个点,其所有的子树中最大的子树节点数最少,那么这个点就是这棵树的重心,删去重心后，生成的多棵树尽可能平衡
思路 ： 给定一颗无根树，将每一个点都设置为根，跑一下dfs，更新自己最大的子数具有的节点数（假定生成的子树中还包含祖先），在这些最大值中选取一个最小值，那个节点就是树的重心。
经典 例题：
3. 树的最长路径
定义 ： 这棵树中距离最远的两个结点之间相隔的距离。注意：是任意两个结点的最远距离，不是树的深度
经典例题：