P4516 [JSOI2018]潜入行动

考虑dp状态 $dp[u][i][0/1][0/1]$ 表示dp到节点 $u$ ， $u$ 的子树里面放了 $i$ 个监听设备， $u$ 自己有没有被放， $u$ 自己有没有被监听。

注意到我们要满足题目的条件，所以只有u的子树内的其他点（不包含u）都被监听，才会算入dp方案数。

接下来是恶心的分类讨论：

$1.dp[u][i][0][0]$ ，此时我们只能有一种选择，即使转移状态是 $u$ 既不被支配，又没有放， $v$ 不能放，否则支配了 $u$ ，但是 $v$ 必须被支配（ $u$ 无法支配 $v$ ），要不然不符合上面我们的条件。

1	Inc(dp[u][j+k][0][0],t[j][0][0]*dp[v][k][0][1]);//v一定要被支配，但是v不能放，否则支配了u

$2.dp[u][i][0][1]$

这里我们根据转移状态，再分两种情况：

$a.转移状态是dp[u][j][0][0]$ ：此时 $v$ 必须放，来支配 $u$ ，而且 $v$ 必须被支配，因为 $u$ 无法支配 $v$ 。

1	Inc(dp[u][j+k][0][1],t[j][0][0]*dp[v][k][1][1]);//如果u只被支配，转移状态是u什么都不放，那么v可以既被支配又放，此时u什么都不放，也不被支配都可以

$b.转移状态是dp[u][j][0][1]$ ：此时 $v$ 放不放无所谓，因为 $u$ 已经被支配了，但是 $v$ 必须被支配，因为 $u$ 无法支配 $v$

1	Inc(dp[u][j+k][0][1],t[j][0][1]*(dp[v][k][1][1]+dp[v][k][0][1]));//转移状态是u被支配，那么v只要被支配即可，注意到v放什么不会影响到u的状态

$3.dp[u][j][1][0]$ 此时转移状态只能是 $u$ 只放而不被支配，后面 $v$ 只要不放即可。

为什么能从 $dp[v][k][0][0]$ 转移而来，是因为 $u$ 放了，可以支配 $v$ ，满足上面的条件。

1	Inc(dp[u][j+k][1][0],t[j][1][0]*(dp[v][k][0][0]+dp[v][k][0][1]));//如果u只被放，转移状态只能是u只被放，所以v不能放，有两种情况

$4.dp[u][j][1][1]$

这里我们根据转移状态，再分两种情况：

$a.转移状态是dp[u][j][1][1]$ 此时随便乱搞，其他四种情况都是合法的。

1	Inc(dp[u][j+k][1][1],t[j][1][1]*(dp[v][k][0][0]+dp[v][k][0][1]+dp[v][k][1][0]+dp[v][k][1][1]));//如果u既被支配又被放，转移状态是u既被支配又被放，那么剩下随便乱搞

$a.转移状态时dp[u][j][1][0]$ 此时 $v$ 只要能够支配 $u$ 即可，所以 $v$ 要放。

1	Inc(dp[u][j+k][1][1],t[j][1][0]*(dp[v][k][1][1]+dp[v][k][1][0]));//转移状态是u只被放，那v必须放，来支配u，注意到v可以不被支配，因为u放了

注意到 $dp$ 过程无法改变 $u$ 节点有没有放的事实，即 $dp[][][0][0/1]$ 只能从 $dp[][][0][0/1]$ 转移而来，同理 $dp[][][1][0/1]$ 只能从 $dp[][][1][0/1]$ 转移而来。

注意此题卡内存，以下代码会MLE。（防抄袭）

#include <bits/stdc++.h>
#define MOD 1000000007
#define MAXN 100005
#define MAXK 105
#define int long long
using namespace std;
inline int read(){
    int x=0,f=1;
    char ch=getchar();
    while (ch<'0'||ch>'9'){
        if (ch=='-') f=-1;
        ch=getchar();
    }
    while (ch>='0'&&ch<='9'){
        x=(x<<3)+(x<<1)+(ch^'0');
        ch=getchar();
    }
    return x*f;
}
vector<int>G[MAXN];
inline void AddEdge(int u,int v){
    G[u].push_back(v);
}
int dp[MAXN][MAXK][2][2],t[MAXK][2][2],sz[MAXN],m;
#define Set(x,y) t[j][x][y]=dp[u][j][x][y];dp[u][j][x][y]=0
inline void Inc(int &a,int b){
    a=(a+b)%MOD;
}
void dfs(int u,int father){
    sz[u]=1;
    dp[u][1][1][0]=dp[u][0][0][0]=1;
    for (register int i=0;i<G[u].size();++i){
        int v=G[u][i];
        if (v==father) continue;
        dfs(v,u);
        int Max1=min(m,sz[u]),Max2=min(m,sz[v]);
        for (register int j=0;j<=Max1;++j){
            Set(0,0);
            Set(0,1);
            Set(1,0);
            Set(1,1);
        }
        for (register int j=0;j<=Max1;++j){
            for (register int k=0;k<=Max2;++k){
                if (j+k>m) continue;
                //printf("In");
                Inc(dp[u][j+k][0][0],t[j][0][0]*dp[v][k][0][1]);//v一定要被支配，但是v不能放，否则支配了u

                Inc(dp[u][j+k][0][1],t[j][0][0]*dp[v][k][1][1]);//如果u只被支配，转移状态是u什么都不放，那么v可以既被支配又放，此时u什么都不放，也不被支配都可以
                Inc(dp[u][j+k][0][1],t[j][0][1]*(dp[v][k][1][1]+dp[v][k][0][1]));//转移状态是u被支配，那么v只要被支配即可，注意到v放什么不会影响到u的状态

                Inc(dp[u][j+k][1][0],t[j][1][0]*(dp[v][k][0][0]+dp[v][k][0][1]));//如果u只被放，转移状态只能是u只被放，所以v不能放，有两种情况

                Inc(dp[u][j+k][1][1],t[j][1][1]*(dp[v][k][0][0]+dp[v][k][0][1]+dp[v][k][1][0]+dp[v][k][1][1]));//如果u既被支配又被放，转移状态是u既被支配又被放，那么剩下随便乱搞
                Inc(dp[u][j+k][1][1],t[j][1][0]*(dp[v][k][1][1]+dp[v][k][1][0]));//转移状态是u只被放，那v必须放，来支配u，注意到v可以不被支配，因为u放了

                //注意到dp过程无法改变u节点有没有放的事实，即dp[][][0][0/1]只能从dp[][][0][0/1]转移而来，同理dp[][][1][0/1]只能从dp[][][1][0/1]转移而来
            }
        }
        sz[u]+=sz[v];
    }
}
#undef int
int main(){
#define int long long
    int n=read();m=read();
    for (register int i=1;i<n;++i){
        int u=read(),v=read();
        AddEdge(u,v);
        AddEdge(v,u);
    }
    dfs(1,1);
    printf("%lld\n",(dp[1][m][0][1]+dp[1][m][1][1])%MOD);//1一定被支配
}