树形DP套路

树形DP套路

1. 以某个节点X为头节点的子树中，分析答案有哪些可能性，并且这种分析是以X的左子树、X的右子树和X整棵树的角度来考虑可能性的
2. 根据第一步的可能性分析，列出所有需要的信息
3. 合并第二步的信息，对左树和右树提出同样的要求，并写出信息结构
4. 设计递归函数，递归函数是处理以X为头节点的情况下的答案。 包括设计递归的basecase，默认直接得到左树和右树的所有信息，以及把可能性做整合，并且要返回第三步的信息结构这四个小步骤

一般都要用到查表