【算法】【DP】树上DP

树上DP

其实树上DP就是记忆化递归，递归的顺序是从叶子节点到根节点，这样就可以保证每个节点的子节点都已经被访问过了。同时，我们可以在递归的过程中，记录每个节点的信息，这样就可以在递归的过程中，直接使用这些信息，而不需要再次递归。在树上进行DP的时候，我们需要考虑两个问题：

1. 状态转移方程
2. 复杂度

状态转移方程

树上DP的状态转移方程，一般是这样的：

dp[father][i] = func(foreach(dp[child_n][j] + Others))

即父节点的状态，是子节点的状态的某种组合。其中，Others是一些其他的信息，比如子节点的个数、子节点的最大值、子节点的最小值等等。