树形dp

树形动态规划（Tree DP）就是在树形结构上进行的动态规划。

在树形结构中，每个节点通常连接着若干子节点，但只有一个父节点。树形DP利用了树的这种结构特点，在动态规划的过程中以节点为单位进行递推，从叶子节点开始，向上逐层计算直至根节点。

由于树形结构天然地包含了递归特性，因此递归式的DP是一种常用的方法。

换根dp

也叫二次扫描法

通常是先计算以0节点为root出发的结果，记为res[0]，而以其它节点为root出发的结果可以通过与res[0]的差值相加得到

其它树形dp