树形DP：
DP巧妙之处在于状态设计，即将多个类似信息放在一起
考虑，这也是DP的最优子结构性质，而树形DP常以记录根
节点信息进行转移，因为通常以根节点子树为DP阶段，而仅
有根节点信息会阶段外信息造成影响。
例1：选课
传统树形背包，利用树的递归性质，即子树（子集合）
之间的独立性分而治之，时间复杂度O(nm^2)考虑时间复杂
度瓶颈。
方案一：序列上的背包DP时间复杂度O(nm)，原因在于
每次合并一种物品，更新答案。树上合并复杂度瓶颈在于n
次合并，每次合并一颗子树的信息，故每次合并都要枚举子
树信息与背包容量，时间复杂度O(nm^2)。
于是考虑降低时间复杂度，根据之前的分析也就是考虑
如何每次只合并一个信息（避免枚举大量信息），于是联想
序列背包的模式，考虑将树上合并转化为序列合并，显然只
需要求出树的dfs序即可，转移时要遵循由子节点转移到父节
点因此向前枚举，注意由于本质上仍然为树形DP，故当不选
当前节点时，上一个状态为f[i+size[aux[i]]]代表如果不选当前
节点则整个子树都无法选择。
思想：时间复杂度瓶颈分析与优化，树的性质，树上问题
转化为序列问题
代码如下：
1 #include <bits/stdc++.h> 2 using namespace std; 3 #define I int 4 #define V void 5 const I N = 5e3 + 3; 6 I n,m,tot,cnt,head[N],to[N],nxt[N],cre[N],aux[N],f[N][N],size[N]; 7 inline V found (I x,I y) { 8 to[++tot] = y,nxt[tot] = head[x],head[x] = tot; 9 } 10 V dfs (I x) { 11 size[x] = 1,aux[cnt++] = x; 12 for (I i(head[x]); i ;i = nxt[i]) 13 dfs (to[i]),size[x] += size[to[i]]; 14 } 15 signed main () { 16 scanf ("%d%d",&n,&m); 17 for (I i(1),x;i <= n; ++ i) scanf ("%d%d",&x,&cre[i]),found (x,i); 18 dfs (0); 19 for (I i(n); i ; -- i) 20 for (I j(m); j ; -- j) 21 f[i][j] = max (f[i + 1][j - 1] + cre[aux[i]],f[i + size[aux[i]]][j]); 22 printf ("%d\n",f[1][m]); 23 }
方案二：较劣的时间复杂度意味着存在冗余转移，于是
考虑优化状态数，发现对于序列问题每个元素由1～m的容量
完成转移，而当转移子树时由1～m^2容量遍历完成转移，而
实际节点数并没有那么多，于是考虑优化转移数。
观察转移方程发现冗余转移在于m^2枚举，于是考虑对于
当前需要转移的子树进行上下界压缩，压缩为其合理转移数，
对于当前子树待转移量为子树大小，而当前树待转移量为已经
合并的子树大小，于是在递归过程中记录两个信息进行状态数
压缩即可，时间复杂度O(nm)考虑转移量即可
代码如下：
1 #include <bits/stdc++.h> 2 using namespace std; 3 #define I int 4 const I N = 5e3 + 3; 5 I f[N][N],s[N],n,m; 6 vector<I> e[N]; 7 I dfs(I u) { 8 I p = 1; 9 f[u][1] = s[u]; 10 for (auto v : e[u]) { 11 I siz = dfs(v); 12 for (I i = min(p, m + 1); i; i--) 13 for (I j = 1; j <= siz && i + j <= m + 1; j++) 14 f[u][i + j] = max(f[u][i + j], f[u][i] + f[v][j]); 15 p += siz; 16 } 17 return p; 18 } 19 I main() { 20 scanf("%d%d", &n, &m); 21 for (I i = 1,x; i <= n; i++) scanf("%d%d", &x, &s[i]),e[x].push_back(i); 22 dfs(0); 23 printf("%d\n",f[0][m + 1]); 24 }
思想：压缩状态数优化时间复杂度，考虑上下界问题