题目分析：
就借助这个题稍微说一下 \(dp\) 套 \(dp\)。
对于 \(dp\) 套 \(dp\) 其解决的问题是：若给定某一具体情况则答案十分好求，现要求对于所有的情况的答案进行统计。
这类问题我们一般称解决这个具体情况的 \(dp\) 为内层 \(dp\)，而对于所有情况进行统计的 \(dp\) 为外层 \(dp\)。
一般的解决方法是：将内层 \(dp\) 的状态直接扔到外层 \(dp\) 的下标上，然后再按需要加入一些新的下标，也就是说假设内层 \(dp\) 的状态为 \(f_1,f_2,f_3\)，那么我们的外层 \(dp\) 则至少应为 \(g_{x,y,z}\)，表示 \(f_1 = x,f_2 = y,f_3 = z\) 时统计的答案，转移时即按照内层 \(dp\) 的转移方式对于下标进行转移。
下面就以这个题为例看看 \(dp\) 套 \(dp\) 的具体应用。
看到这个题的第一眼就可以知道，若给定权值，则树上的最大权独立集是很好求的，就是直接设 \(f_{u,0/1}\) 表示以 \(u\) 为根的子树，\(u\) 节点不选/选的最大权独立集是多少。
考虑 \(f\) 的值并不大，所以可以使用 \(dp\) 套 \(dp\)，即设 \(g_{u,i,j}\) 表示以 \(u\) 为根的子树 \(f_{u,0} = i,f_{u,1} = j\) 的方案数，那么转移就是显然的：（设 \(v\) 为 \(u\) 的儿子节点）
根据树上背包的复杂度分析，这样直接做的复杂度为 \(O(n^4k^4)\)。
对于 \(dp\) 套 \(dp\) 常见优化就是压缩状态或者优化转移。
我们其实可以发现一条性质：\(f_{u,1}\) 不会比 \(f_{u,0}\) 大很多，虽然 \(f_{u,0}\) 可能比 \(f_{u,1}\) 大很多。
也就是说 \(\max(f_{u,1},f_{u,0})-f_{u,0}\) 不大，稍微分析一下就可以发现满足：\(0 \le \max(f_{u,0},f_{u,1}) - f_{u,0}\le val_u = k\)
因为 \(f_{u,0}\) 是在子树上按最优的方式转移的，即使 \(f_{u,1}\) 也是最优的方式转移也只会多 \(val_u\) 的贡献。
（注意这一行状态已经重新设计了）所以我们就可以将内层 \(dp\) 状态重新设计为：\(f_{u,0/1}\) 表示 \(u\) 节点不强制/强制不选的答案，\(g_{u,i,j}\) 表示 \(f_{u,1} = i,f_{u,0} = f_{u,1} + j\) 的方案数。
转移也是显然的：
这样的话复杂度就优化为了 \(O(n^2k^4)\)
需要注意一点就是 \(g_{u,i,j}\) 中 \(j\) 可以为 \(0\)，因为显然不强制不选的最优答案可以为不选。
代码：
点击查看代码
#include<bits/stdc++.h>
#define int long long
using namespace std;
const int N = 1e3+5;
const int K = 7;
const int MOD = 1e9+7;
struct edge{
int nxt,to;
edge(){}
edge(int _nxt,int _to){
nxt = _nxt,to = _to;
}
}e[2 * N];
int n,k,cnt,head[N],sz[N],g[N][N*K][K],f[N*K][K],ans[N*K];
//g[now][i][j] 表示 now 为根的子树，now 随意选不选权值为 i + j，now 强制不选权值为 i 的方案数
void add_edge(int from,int to){
e[++cnt] = edge(head[from],to);
head[from] = cnt;
}
void dfs(int now,int fath){
sz[now] = 1;
for(int i=1; i<=k; i++) g[now][0][i] = 1;
for(int i=head[now]; i;i=e[i].nxt){
int to = e[i].to;
if(to == fath) continue;
dfs(to,now);memset(f,0,sizeof(f));
for(int a=0; a<=sz[now]*k; a++){
for(int b=0; b<=k; b++){
if(g[now][a][b] == 0) continue;
for(int c=0; c<=sz[to]*k; c++){
for(int d=0; d<=k; d++){
f[a+c+d][max(a+b+c,a+c+d)-(a+c+d)] = (f[a+c+d][max(a+b+c,a+c+d)-(a+c+d)] + g[now][a][b] * g[to][c][d])%MOD;
//其实转移就是正常的转移
}
}
}
}
memcpy(g[now],f,sizeof(f));
sz[now] += sz[to];
}
}
signed main(){
// freopen("in.txt","r",stdin);
// freopen("out.txt","w",stdout);
scanf("%lld%lld",&n,&k);
for(int i=1; i<n; i++){
int from,to;scanf("%lld%lld",&from,&to);
add_edge(from,to);add_edge(to,from);
}
dfs(1,0);
for(int i=1; i<=n*k; i++){
for(int j=0; j<=min(i,k); j++){
ans[i] = (ans[i] + g[1][i-j][j])%MOD;
}
}
for(int i=1; i<=n*k; i++) printf("%lld\n",ans[i]);
return 0;
}