题目传送门
题意简述
给出一颗树，有 \(k\) 个传感器需要装到树的节点上，每一个传感器可以控制与当前节点距离为一的所有节点，但是不能控制当前节点，询问在这颗树上布置满 \(k\) 个传感器且控制树上所有节点的合法方案数。
解题思路
考虑树形 \(dp\)，定义 \(dp_{u,x,p,q}\) 表示在以 \(u\) 为根的子树中，布置了 \(x\) 个传感器，\(p\) 表示 \(u\) 节点上是否有传感器，\(q\) 表示 \(u\) 节点是否被控制。
定义好状态后，转移就不是很困难了，每次让 \(u\) 节点和它的子树进行转移即可。可以用背包的思路进行转移。
\[dp_{u,i,p_1,p_2|q_1}=dp_{u,i-j,p_1,q_1}\times dp_{v,j,p_2,q_2}
\]
代码
#include<bits/stdc++.h>
#define ll long long
using namespace std;
const int N=100010;
const int mod=1e9+7;
int n,k,cnt[N],num,siz[N];
int dp[N][105][2][2];
ll f[110][2][2];
vector<int>g[N];
void dfs(int u,int fa){siz[u]=1;dp[u][0][0][0]=dp[u][1][1][0]=1;for(auto v:g[u]){if(v==fa)continue;dfs(v,u);siz[u]+=siz[v];memset(f,0,sizeof(f));for(int i=0;i<=min(siz[u],k);i++){for(int p1=0;p1<=1;p1++){for(int q2=0;q2<=1;q2++){if(!p1&&!q2)continue;for(int q1=0;q1<=1;q1++)for(int j=0;j<=min(siz[v],i);j++)for(int p2=0;p2<=1;p2++)f[i][p1][p2|q1]=(f[i][p1][p2|q1]+(ll)dp[u][i-j][p1][q1]*dp[v][j][p2][q2]%mod)%mod;}}}for(int i=0;i<=min(siz[u],k);i++)for(int p1=0;p1<=1;p1++)for(int q1=0;q1<=1;q1++)dp[u][i][p1][q1]=f[i][p1][q1]%mod;}
}
int main(){ios::sync_with_stdio(false);cin.tie(0);cout.tie(0);cin>>n>>k;for(int i=1;i<n;i++){int u,v;cin>>u>>v;g[u].push_back(v);g[v].push_back(u);cnt[u]++;cnt[v]++;}for(int i=1;i<=n;i++)if(cnt[i]>1)num++;if(num>k*2){cout<<0;return 0;}dfs(1,0);cout<<(dp[1][k][0][1]+dp[1][k][1][1])%mod;return 0;
}