笔记汇总

树形$DP$通常用于解决 有依赖性 $DP$问题，一般做法是将树上每一个结点作为阶段，以不同子树作为下层阶段，进行转移。

由于一棵树上的可能路径不固定起点和终点，数量极大，所以，采用由下往上转移，这样，只需要枚举所有结点一遍（选或不选）。

基础复杂度为 $O(n)$。

因为有依赖关系，必然需要在状态上加上自己，当然一切行为都以 无后效性 为前提。

若是树形$DP$在无向树上跑，就需要用换根$DP$，

因为无向树中，依赖关系不确定，不能保证哪个转移顺序就是最优解，朴素基础复杂度为 $O(n^2)$.

但是，如果我们只是对 相近结点 换根，树的结构变化并不大，

若是将树划分，可以发现不同的部分中变化往往相同，

所以换根$DP$流程为：

1、先指定一个根节点
2、统计子树内的节点对当前节点的贡献
3、统计父亲节点对当前节点的贡献
4、合并统计最终答案

指定根节点是为了确定拓扑结构，由于树的方向不固定，对一点而言，

假定的下方和上方的点都可以影响此点答案，如此并不具有后效性。

又因为无向边等于向下边加向上边，非根点至其附近点连边，贡献为 2 / 3，

这也是将树进行划分，换根时，这两部分贡献会有所变化，统计即可。

子节点更新父节点，是树形的常规操作，

父节点更新子节点，则需要 由上往下 顺次更新，可以包括子节点 异子树下层，

不过要确保此贡献的路径 不包括 子节点自己子树中的路径。

它是 2 + 3 贡献路径的中间结点，3 贡献相连点只有一条，

完全可以 $O(1)$ 解决此时的最优化问题，故而，它既是此时的根。

扩展与变形

简单变形有

方案数统计，

与状态机结合增加依赖关系（需要多开几维数组），

记忆化优化，变化数组状态，变化转移方程，预处理值。

复杂变形有

多价格，增加决策数量，如：树上背包（需要多开几维数组），也可说附带可计数信息，

将树划分成多个部分，分部设计转移方程。

数论累计方案数（一堆神仙玩意）。

结语

树上$DP$在找好结构后，可视作线性$DP$。