树形$DP$ 顾名思义就是在树上进行动态规划

动态规划都是从一个已知状态转移到另一个状态，因此需要选择一种实现顺序。因为开始我们只知道叶子结点的状态，因此我们需要从叶子节点向上更新状态。

SRE实战 互联网时代守护先锋，助力企业售后服务体系运筹帷幄！一键直达领取阿里云限量特价优惠。

在树形$DP$中，一般使用dfs的方式从根结点开始dfs，向其儿子节点递归，直到递归到叶子节点，更新状态。

转移方程的基本形式

$dp[i][j][0\ or\ 1]=（转移方程）$ 其中$i$指以$i$为根的子树，$j$指在这棵子树中选取$j$个节点，$0\ or\ 1$代表选或不选这棵子树

 

扫码关注我们
微信号：SRE实战
拒绝背锅 运筹帷幄