【动态规划 | 树形DP小结】
参考：RioTian
树形DP，一般是在树上进行DP，由于树固有的递归性质，树形DP一般都是递归进行的。这是说我们的树其实是可以递归定义的，树的每一颗子树也是一个完整的树，直到叶子结点可以看做是递归终点。
树形DP是先算子树再进行合并，在实现上与树的后序遍历相似，即左子树->右子树->根节点的遍历顺序，遍历完子树再将子树的值传给父亲，由子树向根上合并。
【例题】
一棵具有
n个点的树(1号为根节点)，求以i为根的子树的大小。DFS
- 设 \(f_i\) 是以\(i\)为根的子树大小，则\(f_i = \sum f[k] + 1\),其中 \(k\) 为 \(i\) 的子节点。
下面是伪代码
void dfs(int u) {
if(u 叶子) f[u] = 1, return;
for (v 是 u 的儿子) {
dfs(v)
f[u] += f[v]
}
f[u] += 1 // 加上本身
}