Steven_Meng's Blog

传送门

考虑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$），要不然不符合上面我们的条件。

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$。

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$

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$，满足上面的条件。

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]$此时随便乱搞，其他四种情况都是合法的。

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$要放。

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一定被支配
}