### 啥是树形DP啊
~~其实我也不知道~~
树形$DP$就是在树上进行的动态规划，~~然后没了~~
然后其他都的跟平常的动态规划一样。
当然，树形$DP$也有两个方向，只是因为他是在树上的$DP$，所以他的两个方向是：
- 从儿子节点到父亲节点（遍历完成图后向叶子结点上更新信息）
- 从父亲节点到儿子节点（预处理完了，重新从父亲节点到儿子节点遍历获取答案）
### 如何实现
树形DP的主要实现形式为：D(大)F(法)S(师)~~之所以不用BFS是因为他太笨了~~
$$
大多数的树形dp的状态是\\dp_{i,j,{0|1}}\\i代表以i为根的字子树\\j表示在这个子树中选取了j个子节点\\0表示当前点不选\\1表示当前点选择\\有时空间比较紧时可以压掉一维(多数为j的那一维)
$$
### 基本的$dp$方程
#### 选择节点类
$$
\begin{cases}
f_{i,0}=f_{j,1}\\
f_{i,1}=max/min(f_{j,0},f_{j,1})
\end{cases}
$$
#### 树形背包类
$$
\begin{cases}
f_{v,k}=f_{v,k}+val\\
f_{u,k}=max/min(f_{u,k},f_{v,k-1})
\end{cases}
$$
差不多就这样吧。
原文：https://www.cnblogs.com/azureheir/p/11186920.html