树形DP一般用于一些树形结构的题目而且是算法竞赛中比较喜欢考察的一个知识点。树形DP入门例题1AcWing 285.没有上司的舞会这题非常简单可称之为树形DP的入门题。显然一个节点有两种状态选参加或不选不参加。那么不妨设fu,1表示节点u被选后u节点及其子树可获得的最大权值fu,0表示节点u不被选的情况下u节点及其子树可获得的最大权值。那么很容易可以推出fu,1fson,0wu其中son表示u的所有子节点。fu,0max(fson,1,fson,0)。那么这个DP顺序显然要按照dfs的顺序来按深度遍历而且要用递归的方式先求出子节点的状态。所以代码就很容易写了#includeiostreamusingnamespacestd;constintN6005;inth[N],f[N][2];inthead[N],to[N],ne[N],idx;boolhfa[N];voidadd(intx,inty){ne[idx]head[x];to[idx]y;head[x]idx;}voiddfs(intu){f[u][1]h[u];for(intihead[u];i;ine[i]){intjto[i];dfs(j);f[u][0]max(f[j][0],f[j][1]);f[u][1]f[j][0];}}intmain(){intn;cinn;for(inti1;in;i)cinh[i];for(inti1;in;i){inta,b;cinab;hfa[a]true;add(b,a);}introot1;while(hfa[root])root;//寻找根节点dfs(root);coutmax(f[root][1],f[root][0]);}例题2洛谷P2899注意读题题干中提到“N头牛N-1个相邻关系”所以必然是树形结构又问最值那么考虑采用树形dp。问题实际上等效于染色一个节点染色后其父节点与子节点也会被染色。那么考虑每个节点的染色或被染色情况分类讨论设自身染色状态为0被父节点染色为1不被父节点染色也不自己染色只能被子节点染色为2。考虑节点u(设其子节点为v父节点为fa)f[u][0]min(f[v][0],f[v][1],f[v][2])1f[u][1]min(f[v][0],f[v][2])注意u为根节点时很特殊由于没有父亲必须要再多加1f[u][2]较难处理先把所有的子节点染色考虑对f[v][2]-f[v][0]排序有负数直接加上相当于取消染色但是不能一直加至少要留一个自己染色的节点碰到非负数直接退出循环即可。最后答案即为min(f[1][0~2])背包类树形DP例题1AcWing 286.选课这题与上一题略有不同这题限定了学生选课的数量刚好为m。所以这题还需要将选课数量也作为状态的一个维度。那么不妨设fx,t表示在以x为根节点的子树中包括x选恰好t门课可获得的最大学分。特别地当t0时x的子树中没有可选的课故fx,00当t0时设Son(x)为x的子节点集合则fx,t∑i1pfyi,ci\sum_{i1}^{p} f_{y_{i},c_{i}}∑i1pfyi,ciscorex其中yi∈\in∈Son(x)且∑i1pcit−1\sum_{i1}^{p} c_{i}t-1∑i1pcit−1。那么这个式子的形式很像之前线性DP中讲到的分组背包DP。我们不妨这样理解一共有p个组每个组里有若干个物品物品的编号为yi体积为ci权值为fyi,ci背包的体积是t-1且每个组里最多挑一个物品。这样思路就很明朗了代码如下#includeiostreamusingnamespacestd;constintN305;inthead[N],to[N],ne[N],w[N],idx;intf[N][N];intn,m;voidadd(intx,inty){ne[idx]head[x];to[idx]y;head[x]idx;}voiddfs(intu){for(intihead[u];i;ine[i]){dfs(to[i]);for(intjm-1;j;j--){for(intk1;kj;k){f[u][j]max(f[u][j],f[u][j-k]f[to[i]][k]);//对数学方程的程序实现有一定的区别//由于此时的f[u][j-k]只经过了前面若干个子节点的更新所以可以直接计算}}}for(intim;i1;i--){//要补上前面选修课程i的学分f[u][i]f[u][i-1]w[u];}}intmain(){cinnm;for(inti1;in;i){intx;cinxw[i];add(x,i);}m;dfs(0);coutf[0][m]endl;return0;}二次扫描与换根法例题1:AcWing 287.积蓄程度这个题目中给的树是一个无根树需要对根进行枚举但显然O(n2)的复杂度无法接受所以我们引入了二次扫描与换根法先考虑以任意一个点为根节点去求答案将得到的答案记为Droot。那么这个时候我们就要考虑怎么求出任意的Fi即以i为根节点的总流量这个时候考虑对于任意一个节点x的子节点y假设我们此时已经求出了Fx那么应该如何导出Fy呢其实很简单直接看蓝书P294就懂了总结二次扫描与换根法的精髓在于先由下到上做一遍dfs求出Droot然后利用D数组由上到下再做一遍dfs求出Fi