树形DP

树上背包

首先，确定一下状态：$dp[i][k][0/1][0/1]$ 代表是以第 $i$ 个节点为树根，其中放了 $k$ 个特工，该节点被父亲 / 儿子观察，该节点放 / 不放特工。
其中，为确保状态不重，状态 $(i,k,0,0/1)$ 的所有儿子均不可放特工。
确定状态之后，我们来看转移。

【转移】

先说 $dp[i][k][0][0]$。

对于儿子 $v$,应该有前面放 $k-j$ 个成立的方案数 $\times$ $v$ 节点放 $j$ 个、被儿子看、自身不放的方案数，即 $dp[i][k][0][0]=\sum dp[i][k-j][0][0]\ \times \ dp[v][j][1][0]$。

二说 $dp[i][k][0][1]$。

对于儿子 $v$,应该有前面放 $k-j$ 个成立的方案数 $\times$ $v$ 节点放 $j$ 个、被父亲 / 儿子看、自身不放的方案数，即 $dp[i][k][0][1]=\sum dp[i][k-j][0][1] \times (dp[v][j][1][0]+dp[v][j][0][0])$。

三说 $dp[i][k][1][0]$。

对于儿子 $v$,应该有：
1.前面放 $k-j$ 个成立的方案数 $\times$ $v$ 节点放 $j$ 个、被儿子看、自身放 / 不放的方案数；
2.前面放 $k-j$ 个，但 $i$ 号节点仍未被观察的方案数 $*$ $v$ 节点放 $j$ 个、被儿子看、自身放的方案数；
即：$dp[i][k][1][0]=\sum (dp[i][k-j][1][0] \times (dp[v][j][1][0]+dp[v][j][1][1]) + dp[i][k-j][0][0] \times dp[v][j][1][1])$

最后说 $dp[i][k][1][1]$。

对于儿子 $v$,应该有：
1.前面放 $k-j$ 个成立的方案数 $\times$ $v$ 节点放 $j$ 个、被父亲 / 儿子看、自身放 / 不放的方案数；
2.前面放 $k-j$ 个，但 $i$ 号节点仍未被观察的方案数 $*$ $v$ 节点放 $j$ 个、被父亲 / 儿子看、自身放的方案数；
即：$dp[i][k][1][1]=\sum (dp[i][k-j][1][1] \times (dp[v][j][1][0]+dp[v][j][1][1]+dp[v][j][0][0]+dp[v][j][0][1]) + dp[i][k-j][0][1]* (dp[v][j][1][1]+dp[v][j][0][1])$

最最后，注意 $k$ 倒着枚举,$j$ 从 $0$ 开始枚举，答案是 $dp[root][k][1][0]+dp[root][k][1][1]$ （ $root$ 为将无根树转成有根树时的树根），就可以了。

贴出代码：（因常数过大导致TLE，O2过了）

#include <bits/stdc++.h>
using namespace std;
int w;//题目中的k
const int mod = 1e9 + 7;
vector<int>e[100001];//建树
int size[100001];//子树大小
unsigned int dp[100001][101][2][2];//long long 会MLE

void dfs1(int i, int fa) {
	size[i] = 1;
	for (int j = 0; j < e[i].size(); j++)
		if (e[i][j] != fa) {
			dfs1(e[i][j], i);
			size[i] += size[e[i][j]];
		}
}

void dfs2(int i, int fa) {
	for (int j = 0; j < e[i].size(); j++)
		if (e[i][j] != fa)
			dfs2(e[i][j], i);
	dp[i][0][0][0] = dp[i][1][0][1] = 1;
	int qwq = 1;
	for (int j = 1; j <= e[i].size(); j++)//转移
		if (e[i][j - 1] != fa) {
			qwq += size[e[i][j - 1]];
			for (int k = min(w, qwq); k >= 0; k--) {
				unsigned long long int ans1 = 0, ans2 = 0, ans3 = 0, ans4 = 0;
				for (int x = 0; x <= min(k, size[e[i][j - 1]]); x++) {
					int v = e[i][j - 1];
					if (k - x > qwq - size[v])
						continue;
					(ans1 += ((unsigned long long )dp[i][k - x][0][0] *
					          (dp[v][x][1][0]))) %= mod;

					(ans2 += ((unsigned long long )dp[i][k - x][0][1] *
					          (dp[v][x][1][0]
					           + dp[v][x][0][0]))) %= mod;

					(ans3 += ((unsigned long long )dp[i][k - x][1][0] * (dp[v][x][1][0] + dp[v][x][1][1])
					          + (unsigned long long )dp[i][k - x][0][0] * dp[v][x][1][1])) %= mod;

					(ans4 += ((unsigned long long )dp[i][k - x][1][1] * (dp[v][x][1][0] + dp[v][x][0][0]
					                                + dp[v][x][1][1] + dp[v][x][0][1])
					          + (unsigned long long )dp[i][k - x][0][1] * (dp[v][x][1][1] + dp[v][x][0][1]))) %= mod;
				}
				dp[i][k][0][0] = ans1;
				dp[i][k][0][1] = ans2;
				dp[i][k][1][0] = ans3;
				dp[i][k][1][1] = ans4;
			}

		}
}

int main() {
	int n;
	cin >> n >> w;
	for (int i = 1; i < n; i++) {
		int a, b;
		scanf("%d%d", &a, &b);
		e[a].push_back(b);
		e[b].push_back(a);
	}
	dfs1(1, 0);
	dfs2(1, 0);
	cout << (dp[1][w][1][0] + dp[1][w][1][1]) % mod;
	return 0;
}

E82 树上背包 P4516 JSOI2018 潜入行动

// 树上背包 O(n*k)
#include<bits/stdc++.h>
using namespace std;

typedef long long LL;
const int N=100005,mod=1000000007;
int n,k,sz[N];
int f[N][105][2][2],g[105][2][2];
vector<int> e[N];

int add(LL x,LL y){
  return (x+y)%mod;
}
void dfs(int u,int fa){
  sz[u]=1;
  f[u][0][0][0]=f[u][1][1][0]=1;
  for(auto v:e[u]){
    if(v==fa) continue;
    dfs(v,u);
    for(int i=0;i<=min(sz[u],k);++i){
      g[i][0][0]=f[u][i][0][0], f[u][i][0][0]=0;
      g[i][0][1]=f[u][i][0][1], f[u][i][0][1]=0;
      g[i][1][0]=f[u][i][1][0], f[u][i][1][0]=0;
      g[i][1][1]=f[u][i][1][1], f[u][i][1][1]=0;
    }
    for(int i=0;i<=min(sz[u],k);++i){
      for(int j=0;j<=min(sz[v],k-i);++j){
        f[u][i+j][0][0]=add(f[u][i+j][0][0],
                            g[i][0][0]*1ll*f[v][j][0][1]);
        f[u][i+j][1][0]=add(f[u][i+j][1][0],
                            g[i][1][0]*(1ll*f[v][j][0][0]+f[v][j][0][1]));                            
        f[u][i+j][0][1]=add(f[u][i+j][0][1],
                            g[i][0][0]*1ll*f[v][j][1][1]
                           +g[i][0][1]*(1ll*f[v][j][1][1]+f[v][j][0][1]));
        f[u][i+j][1][1]=add(f[u][i+j][1][1],
                           +g[i][1][0]*(1ll*f[v][j][1][0]+f[v][j][1][1])
                           +g[i][1][1]*(1ll*f[v][j][0][0]+f[v][j][0][1]
                                           +f[v][j][1][0]+f[v][j][1][1]));
      }
    }
    sz[u]+=sz[v];
  }
}
int main(){
  scanf("%d%d",&n,&k);
  for(int i=1,u,v;i<n;++i){
    scanf("%d%d",&u,&v);
    e[u].push_back(v);
    e[v].push_back(u);
  }
  dfs(1,0);
  printf("%d\n",(f[1][k][0][1]+f[1][k][1][1])%mod);
}