树上dp
什么是树上dp？字面意思，在树上做dp
但是这个描述不准确，更准确应该是树形dp，树上dp可能只是在树上，有一个dp，不一定是树状转移状态的
状态转移的方向：自顶向下/自底向上
一个自顶向下的例子：树上差分
自顶向下时一个结点的多个子结点会共用一个dp状态栈，所以需要利用回溯的性质
自底向上时一个结点会从多个子结点来转移状态，所以状态转移方程会更复杂；且子结点树可能是\(O(n)\)的，对于关于子结点数\(k\)时间复杂度\(\Omega(k^{1+\epsilon})\)的转移计算方法，菊花树会爆，此时要考虑在子结点上维护一些数据结构或者启发式合并状态或者设计逐结点转移方程
树形dp
例题：没有上司的舞会
题解
一个结点出不出席影响子结点的出席情况，所以设计状态时要分类讨论
f[i]代表考虑结点i子树来参加舞会且i本身出席的最大快乐指数，g[i]代表考虑结点i子树来参加舞会且i本身不出席的最大快乐指数，那么我们可以得到转移方程
\[ f[i] = r[i] + \sum{j:i} g[j] \]
\[ g[i] = \sum{j:i} \max (f[j], g[j]) \]
例题：树上染色
题解
这里黑色结点数类似于背包的感觉，必须选出k个，所以状态转移自然有两维
设计状态的时候，我们发现如果f[i][j]代表给结点i的子树染色，其中j个结点为黑色，能够获得多少收益，那么很难计算跨子树部分的收益，所以改为统计能够有多少贡献
考虑具体对贡献值的定义时，我们发现距离的贡献可以被拆解到树边的贡献，所以只需要统计子树内所有边有多少贡献就可以了
那么在状态转移时，除了合并子树贡献，还有一些连接根和儿子的边的贡献没被计算，这些边贡献和边下染了几个黑结点有关
最后类似树上背包依次把每个儿子的贡献并进去就可以了
f[i]代表考虑结点i子树来参加舞会且i本身出席的最大快乐指数，g[i]代表考虑结点i子树来参加舞会且i本身不出席的最大快乐指数，那么我们可以得到转移方程
\[ f[i] = r[i] + \sum{j:i} g[j] \]
\[ g[i] = \sum{j:i} \max (f[j], g[j]) \]
作业：叶结点划分CF1146F，连通块个数，树上游戏(染色树每个点到所有点路径上颜色数之和)P2664
重心
树的重心(割掉每条边得到重心点权和)P5666
枚举边，边下面考虑重心在重链上单调性，边外面重心位于dfs序中点祖先链上+倍增二分求重心or重心向重儿子移动(边在重子树上则向次重儿子移动)
拎出重心，枚举点，转化为该点子树外多少子树重量介于区间内，dfs序上归并树/集合树状数组or容斥，前缀和求总数-树状数组计算进点和回溯差值
淀粉质
淀粉质模板(边权树上距离为k点对是否存在)P3806
作业：Tree(边权树上距离<=k点对数)P4178，边权树上每个点距离k内点权最大值P6329弱化
直径
捉迷藏P2056(不用淀粉质？)
作业：树上路径(边权树上前k大距离)P12692