Description
外星人又双叒叕要攻打地球了，外星母舰已经向地球航行！这一次，JYY已经联系好了黄金舰队，打算联合所有JSO
Ier抵御外星人的进攻。在黄金舰队就位之前，JYY打算事先了解外星人的进攻计划。现在，携带了监听设备的特工
已经秘密潜入了外星人的母舰，准备对外星人的通信实施监听。外星人的母舰可以看成是一棵n个节点、n-1条边的
无向树，树上的节点用1,2...n编号。JYY的特工已经装备了隐形模块，可以在外星人母舰中不受限制地活动，可以
神不知鬼不觉地在节点上安装监听设备。如果在节点u安装监听设备，则JYY能够监听与u直接相邻所有的节点的通
信。换言之，如果在节点u安装监听设备，则对于树中每一条边(u,v)，节点v都会被监听。特别注意放置在节点u的
监听设备并不监听u本身的通信，这是JYY特别为了防止外星人察觉部署的战术。
JYY的特工一共携带了k个监听设备，现在JYY想知道，有多少种不同的放置监听设备的方法，能够使得母舰上所有
节点的通信都被监听？为了避免浪费，每个节点至多只能安装一个监听设备，且监听设备必须被用完。
Solution
设 \(f[x][i][0/1][0/1]\) 表示 \(x\) 子树内的点中选了 \(i\) 个点,\(x\) 是否选, \(x\) 是否被儿子覆盖
简单转移即可
#include<bits/stdc++.h>using namespace std;template<class T>void gi(T &x){ ???int f;char c; ???for(f=1,c=getchar();c<'0'||c>'9';c=getchar())if(c=='-')f=-1; ???for(x=0;c<='9'&&c>='0';c=getchar())x=x*10+(c&15);x*=f;}const int N=1e5+10,mod=1e9+7;int n,K,head[N],nxt[N*2],to[N*2],num=0,sz[N],f[N][105][2][2],g[105][2][2];inline void link(int x,int y){nxt[++num]=head[x];to[num]=y;head[x]=num;}inline void dfs(int x){ ???sz[x]=f[x][1][1][0]=f[x][0][0][0]=1; ???for(int P=head[x],u;P;P=nxt[P]){ ???????if(sz[u=to[P]])continue; ???????dfs(u); ???????for(int i=min(sz[x],K);i>=0;i--) ???????????for(int j=0;j<2;j++)for(int k=0;k<2;k++)g[i][j][k]=f[x][i][j][k],f[x][i][j][k]=0; ???????for(int i=min(sz[x],K);i>=0;i--) ???????????for(int j=min(sz[u],K-i);j>=0;j--){ ???????????????int sum=(1ll*f[u][j][0][0]+f[u][j][0][1]+f[u][j][1][0]+f[u][j][1][1])%mod; ???????????????f[x][i+j][1][0]=(f[x][i+j][1][0]+1ll*g[i][1][0]*(f[u][j][0][0]+f[u][j][0][1]))%mod; ???????????????f[x][i+j][1][1]=(f[x][i+j][1][1]+1ll*g[i][1][1]*sum+1ll*g[i][1][0]*(f[u][j][1][0]+f[u][j][1][1]))%mod; ???????????????f[x][i+j][0][1]=(f[x][i+j][0][1]+1ll*g[i][0][0]*f[u][j][1][1]+1ll*g[i][0][1]*(f[u][j][1][1]+f[u][j][0][1]))%mod; ???????????????f[x][i+j][0][0]=(f[x][i+j][0][0]+1ll*g[i][0][0]*f[u][j][0][1])%mod; ???????????} ???????sz[x]+=sz[u]; ???}}int main(){ ?freopen("pp.in","r",stdin); ?freopen("pp.out","w",stdout); ?int x,y; ?cin>>n>>K; ?for(int i=1;i<n;i++){ ?????gi(x);gi(y); ?????link(x,y);link(y,x); ?} ?dfs(1); ?printf("%d\n",(f[1][K][0][1]+f[1][K][1][1])%mod); ?return 0;}bzoj 5314: [Jsoi2018]潜入行动
原文地址：https://www.cnblogs.com/Yuzao/p/9060058.html