一棵树上放k个摄像头，每个摄像头可以监视和这个点邻接的所有点但不能监视它本身
求监视到所有点的方案数
sol：
树形dp，思路很简单，$dp[i][j][0/1][0/1]$表示$i$号点的子树里放了$j$个摄像头，$[这个点是否已经被监视到]$，$[这个点放没放摄像头]$的方案数
转移的时候很麻烦，分后面0101四种情况讨论一下
树形背包就可以了
1.没放，也没被监视，方案数 = 没被剩下监视的方案数 * 这颗子树被监视没放的方案数
2.放了，但没被监视，方案数 = 放了但没被剩下监视的方案数 * 这棵子树不放的方案数
3.没放，但被监视了，方案数 = 没放没被剩下监视的方案数 * 这棵子树又放又被监视的方案数 + 这棵子树放了的方案数 * 没放被剩下监视的方案数
4.放了，也被监视了，方案数 = 放了被剩下监视的方案数 * 这棵子树总方案数 + 放了但没被监视的方案数 * 这棵子树放了的方案数
md这题解写的我头壳疼
还有，这道题卡空间，开LL会MLE
只好unsigned int...
#include<bits/stdc++.h> #define LL unsigned long long using namespace std; inline int read() { int x = 0,f = 1;char ch = getchar(); for(;!isdigit(ch);ch = getchar())if(ch == '-')f = -f; for(;isdigit(ch);ch = getchar())x = 10 * x + ch - '0'; return x * f; } const int maxn = 1e5 + 5; const int mod = 1e9 + 7; int n,k; int size[maxn]; int first[maxn],targ[maxn << 1],nx[maxn << 1],cnt; inline void add(int u,int v) { targ[++cnt] = v; nx[cnt] = first[u]; first[u] = cnt; } inline void ins(int u,int v){add(u,v);add(v,u);} inline void Add(unsigned int &x,LL y){y %= mod;x=(x+y>=mod?x+y-mod:x+y);} unsigned int f[maxn][105][2][2];LL tmp[105][2][2]; void dfs(int x,int fa) { size[x] = 1;f[x][0][0][0] = f[x][1][0][1] = 1; for(int ee = first[x];ee;ee = nx[ee]) { int to = targ[ee]; if(to == fa)continue; dfs(to,x); for(int i=0;i<=min(k,size[x]);i++) for(int j=0;j<=1;j++) for(int kk=0;kk<=1;kk++)tmp[i][j][kk] = f[x][i][j][kk],f[x][i][j][kk] = 0; for(int i=0,r1=min(size[x],k);i<=r1;i++) for(int j=0,r2=min(size[to],k);i+j<=k&&j<=r2;j++) { Add(f[x][i + j][0][0],(LL)tmp[i][0][0] * f[to][j][1][0] % mod); Add(f[x][i + j][0][1] ,(LL)((f[to][j][0][0] * tmp[i][0][1]) + (LL)(f[to][j][1][0] * tmp[i][0][1])) % mod); Add(f[x][i + j][1][0] ,(LL)(((f[to][j][1][0] + f[to][j][1][1])) * tmp[i][1][0] + (LL)(f[to][j][1][1] * tmp[i][0][0])) % mod); Add(f[x][i + j][1][1] ,(LL)(tmp[i][1][1] * ((LL)(f[to][j][1][1] + f[to][j][0][1] + f[to][j][0][0] + f[to][j][1][0])) + tmp[i][0][1] * ((LL)(f[to][j][1][1] + f[to][j][0][1]))) % mod); } size[x] += size[to]; } } int main() { n = read(),k = read(); int u,v; for(int i=2;i<=n;i++) { u = read(),v = read(); ins(u,v); } dfs(1,0); printf("%d ",(f[1][k][1][0] + f[1][k][1][1]) % mod); }