[JSOI2018]潜入行动
树形背包。
这道题考察树形背包中枚举上下界（时间复杂度&代码实现）和细节上的一些东西。
定义状态：(dp[u][i][0/1][0/1])，代表以结点(u)为根的子树中除了根节点其它节点均被监控用了恰好(i)个监控，其中第一个(0/1)代表该结点是否放了监控；第二个(0/1)该结点是否也被监控。
大概有这样一些方程：
[dp[u][i+j][0][0]=sum_{vin son(u)} {dp[u][i][0][0]*dp[v][j][0][1]}
]
这个式子代表该结点既不放监控也不被子结点监控（换言之，想要合法父结点必须放监控），那么子结点肯定不能放监控，并且为了保证状态合法性，必须被监控。
还有一点：为什么表达式中用(i+j)表示被更新状态恰恰好使用的监控数呢？
那是因为（其实您如果写成其他的形式也都可以）这样的表示方便最终的枚举。换言之，枚举的边界方便“卡”。
同理：
[dp[u][i+j][0][1]=sum_{vin son(u)}{dp[u][i][0][0]*dp[v][j][1][1]+dp[u][i][0][1]*(dp[v][j][0][1]+dp[v][j][1][1])}
]
这个式子利用树形背包的树合并思想：合并两个“泛化物品”即可。
那么，我们对于当前泛化物品讨论：1. 如果当前的泛化物品根节点没有被监控，那么它的子结点放。
- 如果被监控了，那就都可以，放和不放两种情况一同记下来。
还能得到：
[dp[u][i+j][1][0]=sum_{vin son(u)}{dp[u][i][1][0]*(dp[v][j][0][0]+dp[v][j][0][1])}
]
它的儿子不能放监控，然而它的子结点可以被监控也可以不被。
最后&有：
[dp[u][i+j][1][1]=sum_{vin son(u)}{dp[u][i][1][0]*(dp[v][j][1][0]+dp[v][j][1][1])+dp[u][i][1][1]*(dp[v][j][0][0]+dp[v][j][0][1]+dp[v][j][1][0]+dp[v][j][1][1])}
]
边界条件（注意点）：
-
显然，如果该结点是叶子节点，那么其他都是零，只有：(dp[u][1][1][0]=1)和(dp[u][0][0][0]=1)；
-
上述方程中(i)和(j)中，(i(i<=K))不能超过当前(u)的总结点数（因为是动态合并的嘛），(j(j<=K))不能超过(v)的总结点数，并且(i+j<=K)；
-
转移的时候要建立一个临时数组（避免各种玄学错误、调试方便）
代码如下：
#include<iostream>
#include<cstring>
#include<vector>
#include<cstdio>
#include<cmath>
using namespace std;
typedef long long LL;
const int N = 1e5 + 5, K = 100 + 5, mod = 1e9 + 7;
template <typename T> void read(T &x)
{
bool mark = false;
char ch = getchar();
for(; ch < '0' || ch > '9'; ch = getchar()) if(ch == '-') mark = true;
for(x = 0; ch >= '0' && ch <= '9'; ch = getchar()) x = (x << 3) + (x << 1) + ch - '0';
if(mark) x = -x;
return;
}
vector <int> G[N];
int n, lim[N] = {}, k, newdp_u[K][2][2], dp[N][K][2][2] = {};
inline int add(int x, LL y)
{
x %= mod, y %= mod;
y = (y + mod) % mod;
x += y;
while(x >= mod) x -= mod;
return x;
}
void dfs(int u, int Fa)
{
int n_lim = 1, v;
lim[u] = dp[u][0][0][0] = dp[u][1][1][0] = 1;
for(int cur = 0; cur < G[u].size(); ++ cur)
{
v = G[u][cur];
if(v == Fa) continue;
dfs(v, u);
n_lim = min(k, lim[u] + lim[v]);//套路设置：总限制
for(int i = 0; i <= lim[u]; ++ i)
for(int j = 0; j <= lim[v] && i + j <= n_lim; ++ j)
{
newdp_u[i + j][0][0] = add(newdp_u[i + j][0][0], 1ll * dp[u][i][0][0] * dp[v][j][0][1] % mod);
newdp_u[i + j][1][0] = add(newdp_u[i + j][1][0], 1ll * dp[u][i][1][0] * (dp[v][j][0][0] + dp[v][j][0][1]) % mod);
newdp_u[i + j][0][1] = add(newdp_u[i + j][0][1], 1ll * dp[u][i][0][0] * dp[v][j][1][1] % mod + 1ll * dp[u][i][0][1] *
(dp[v][j][0][1] + dp[v][j][1][1]) % mod);
newdp_u[i + j][1][1] = add(newdp_u[i + j][1][1], 1ll * dp[u][i][1][0] * (dp[v][j][1][0] + dp[v][j][1][1]) % mod + 1ll * dp[u][i][1][1] *
((dp[v][j][0][0] + dp[v][j][0][1]) % mod + (dp[v][j][1][0] + dp[v][j][1][1]) % mod) % mod);
}
for(int i = 0; i <= n_lim; ++ i)
for(int x = 0; x < 2; ++ x)
for(int y = 0; y < 2; ++ y)
dp[u][i][x][y] = newdp_u[i][x][y], newdp_u[i][x][y] = 0;
lim[u] = n_lim;
}
return;
}
int main()
{
read(n), read(k);
int u, v;
for(int i = 0; i <= n; ++ i) G[i].clear();
for(int i = 1; i < n; ++ i)
{
read(u), read(v);
G[u].push_back(v), G[v].push_back(u);
}
dfs(1, 0);
printf("%d
", (dp[1][k][0][1] + dp[1][k][1][1]) % mod);
return 0;
}