又是荒废在搭$blog$的一天，不过成功把稳稳嫖了
。
设$f(i,j,0/1,0/1)$为在$i$子树中安$j$个装置、$i$是否有儿子安、$i$是否安、满足$i$子树除$i$以外所有点均被覆盖的方案数。
搞个树形背包大力转移：
$f(i,j,0,0)=\sum\limits_{x\in son(i),k}f(x,k,1,0)\times f(i,j-k,0,0)$
$f(i,j,0,1)=\sum\limits_{x\in son(i),k}(f(x,k,0,0)+f(x,k,1,0))\times f(i,j-k,0,1)$
$f(i,j,1,0)=\sum\limits_{x\in son(i),k}f(x,k,1,0)\times f(i,j-k,1,0)+(f(i,j-k,0,0)+f(i,j-k,1,0))\times f(x,k,1,1)$
$f(i,j,1,1)=\sum\limits_{x\in son(i),k}(f(x,k,0,0)+f(x,k,1,0))\times f(i,j-k,1,1)+(f(x,k,0,1)+f(x,k,1,1))\times(f(i,j-k,0,1)+f(i,j-k,1,1))$
（转移就是个普及$DP$我也懒得解释了）
这还没完，有一个坑点是不能直接跟树形背包一样直接更新$f$，需要先开个数组把存新的$f$，最后直接覆盖上去。
一开始以为和普通背包一样是防止状态更新顺序混乱，然而倒序循环$j$还是不对。通过输出$f$数组会发现某些状态在加入儿子后会变得不合法，而直接更新$f$是在原有基础上累加方案，不能过滤掉不合法的状态。
复杂度$O(nk)$。然而不知道为啥和树形背包一样枚举$j,k$会被链卡到$5s$，改成刷表转移才过。
代码：
#include <iostream>
#include <cstdio>
#include <algorithm>
#include <cmath>
#include <cstring>
#define maxn 100003
#define inf 0x3f3f3f3f
const int mod = 1e9 + 7;
using namespace std;
inline int read(){
int x=0,y=0;
char ch=getchar();
while(ch<'0'||ch>'9'){if(ch=='-')y=1;ch=getchar();}
while(ch>='0'&&ch<='9')x=(x<<1)+(x<<3)+(ch^48),ch=getchar();
return y?-x:x;
}
int f[maxn][102][2][2],g[102][2][2],siz[maxn],h[maxn],num,m;
struct edge{
int pre,to;
}e[maxn<<1];
inline void add(int from,int to){
e[++num]=(edge){h[from],to};
h[from]=num;
}
inline void up(int &x,long long y){if(y>=mod)y%=mod;x=(x+y)%mod;}
void dp(int node=1){
siz[node]=f[node][1][0][1]=f[node][0][0][0]=1;
for(register int i=h[node],x;i;i=e[i].pre){
x=e[i].to;
if(siz[x])continue;
dp(x);
for(register int j=min(siz[node],m);~j;--j)
for(register int k=min(siz[x],m-j);~k;--k){
up(g[j+k][0][0],1ll*f[x][k][1][0]*f[node][j][0][0]);
up(g[j+k][0][1],1ll*(f[x][k][0][0]+f[x][k][1][0])*f[node][j][0][1]);
up(g[j+k][1][0],1ll*f[x][k][1][0]*f[node][j][1][0]+1ll*f[x][k][1][1]*(f[node][j][0][0]+f[node][j][1][0]));
up(g[j+k][1][1],1ll*(f[x][k][0][0]+f[x][k][1][0])*f[node][j][1][1]+1ll*(f[x][k][0][1]+f[x][k][1][1])*(f[node][j][0][1]+f[node][j][1][1]));
}
siz[node]+=siz[x];
for(register int j=min(siz[node],m);~j;--j){
f[node][j][0][0]=g[j][0][0],g[j][0][0]=0;
f[node][j][0][1]=g[j][0][1],g[j][0][1]=0;
f[node][j][1][0]=g[j][1][0],g[j][1][0]=0;
f[node][j][1][1]=g[j][1][1],g[j][1][1]=0;
}
}
}
int main(){
int n=read();
m=read();
for(register int i=1,x,y;i<n;++i)x=read(),y=read(),add(x,y),add(y,x);
dp();
printf("%d\n",(f[1][m][1][0]+f[1][m][1][1])%mod);
}
