Luogu

LOJ

分析

设 $dp_{i,j,0/1,0/1}$ 表示以 $i$ 为根的子树，已经放了 $j$ 个监听设备，$i$ 是否放了监听设备，$i$ 是否被子树中的点监听时子树中除 $i$ 外的所有点都被监听的方案数。

转移类似于树形背包，需要将各种情况讨论清楚。

边界为 $dp_{i,0,0,0}=dp_{i,1,1,0}=1$。

代码

// ===================================
//   author: M_sea
//   website: http://m-sea-blog.com/
// ===================================
#include <bits/stdc++.h>
#define re register
using namespace std;

inline int read() {
    int X=0,w=1; char c=getchar();
    while (c<'0'||c>'9') { if (c=='-') w=-1; c=getchar(); }
    while (c>='0'&&c<='9') X=X*10+c-'0',c=getchar();
    return X*w;
}

const int N=100000+10,K=100+10;
const int mod=1e9+7;
inline void add(int& x,int y) { x=(x+y)%mod; }

int n,L;

struct edge { int v,nxt; } e[N<<1];
int head[N];
inline void addEdge(int u,int v) {
    static int cnt=0;
    e[++cnt]=(edge){v,head[u]},head[u]=cnt;
}

int sz[N],dp[N][K][2][2],tmp[K][2][2];
inline void dfs(int u,int fa) {
    sz[u]=1,dp[u][0][0][0]=dp[u][1][1][0]=1;
    for (re int i=head[u];i;i=e[i].nxt) {
        int v=e[i].v; if (v==fa) continue;
        dfs(v,u);
        memset(tmp,0,sizeof(tmp));
        for (re int j=0;j<=min(L,sz[u]);++j)
            for (re int k=0;k<=min(L-j,sz[v]);++k) {
                add(tmp[j+k][0][0],1ll*dp[u][j][0][0]*dp[v][k][0][1]%mod);
                add(tmp[j+k][0][1],(1ll*dp[u][j][0][1]*dp[v][k][0][1]+
                                    1ll*dp[u][j][0][1]*dp[v][k][1][1]+
                                    1ll*dp[u][j][0][0]*dp[v][k][1][1])%mod);
                add(tmp[j+k][1][0],(1ll*dp[u][j][1][0]*dp[v][k][0][0]+
                                    1ll*dp[u][j][1][0]*dp[v][k][0][1])%mod);
                add(tmp[j+k][1][1],(1ll*dp[u][j][1][0]*dp[v][k][1][0]+
                                    1ll*dp[u][j][1][0]*dp[v][k][1][1]+
                                    1ll*dp[u][j][1][1]*dp[v][k][0][0]+
                                    1ll*dp[u][j][1][1]*dp[v][k][0][1]+
                                    1ll*dp[u][j][1][1]*dp[v][k][1][0]+
                                    1ll*dp[u][j][1][1]*dp[v][k][1][1])%mod);
            }
        memcpy(dp[u],tmp,sizeof(tmp));
        sz[u]+=sz[v];
    }
}

int main() {
    n=read(),L=read();
    for (re int i=1;i<n;++i) {
        int u=read(),v=read();
        addEdge(u,v),addEdge(v,u);
    }
    dfs(1,0); printf("%d\n",(dp[1][L][0][1]+dp[1][L][1][1])%mod);
    return 0;
}