树形DP-526互联

一.定义
树形dp，顾名思义，即为树上的DP。
二.分类
1.普通树形dp
2.换根dp
三.一些常用技巧及思想
1.补集转化思想：就是数学常用的“正难则反”。
例：一棵树，每个点有权值，要求选一个连通块，此连通块包含最大权值的方案数。
解:将包含最大权值的连通块个数转化为所有连通块个数减去不包含最大权值的连通块
2.贡献思想：将一个大问题转化为小问题对大问题的贡献之和
例：一棵树，求所有至少一个端点是叶节点的路径的权值和的和
解：将问题转化为每条边对于问题的贡献即可
3.递归：将父节点的问题转化为子节点的问题，再合并
4.设计状态：一般一个节点x的状态都与其自身有关，方便转移
5.树形dp可与背包结合，即为树形背包