题意:一棵树选择恰好k个结点放置监听器
每个监听器只能监听相邻的节点
问能使得所有节点被监听的种类数
题解:反正就是很well-known的树形DP了
至于时间复杂度为什么是nk 不会不学
很好想到四维dp 在x节点放置j个 x有没有放监听器 x有没有被监听
瞎搞搞就好了 头写昏了转移就抄别人了的TAT
关键是这个题开ll会mle 不开会爆int 取%频繁还会tle
西安太热了!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!
#include <stdio.h> #include <algorithm> #include <iostream> #include <string.h> using namespace std; typedef long long ll; const ll mod = 1000000007; int n, k; struct node { int to, nex; }E[200005]; int head[100005]; int sz[100005]; int dp[100002][102][2][2]; //放不放 被占用没 ll tmp[102][2][2]; inline void add(int &x,ll y) { if(x + y >= mod) x = x + y - mod; else x = x + y; } void dfs(int x, int fa) { sz[x] = 1; dp[x][1][1][0] = 1; //放 dp[x][0][0][0] = 1; //不放 int c = head[x]; for(int i = c; i; i = E[i].nex) { int v = E[i].to; if(v == fa) continue; dfs(v, x); int tx = min(k, sz[x]); int tv = min(k, sz[v]); for(int j = 0; j <= tx; j++) for(int jj = 0; jj < 2; jj++) for(int jjj = 0; jjj < 2; jjj++) tmp[j][jj][jjj] = dp[x][j][jj][jjj], dp[x][j][jj][jjj] = 0; for(int j = 0; j <= tx; j++) { for(int jj = 0; jj <= tv && j + jj <= k; jj++) { add(dp[x][j + jj][0][0], tmp[j][0][0] * dp[v][jj][0][1] % mod); add(dp[x][j + jj][0][1], (tmp[j][0][0] * dp[v][jj][1][1] + tmp[j][0][1] * (dp[v][jj][0][1] + dp[v][jj][1][1]))%mod); add(dp[x][j + jj][1][0], tmp[j][1][0] * (dp[v][jj][0][0] + dp[v][jj][0][1]) % mod); add(dp[x][j + jj][1][1], (tmp[j][1][0] * (dp[v][jj][1][0] + dp[v][jj][1][1]) + tmp[j][1][1] * (dp[v][jj][0][0] + dp[v][jj][1][0]) + tmp[j][1][1] * (dp[v][jj][0][1] + dp[v][jj][1][1]))%mod); } } sz[x] += sz[v]; } } int main() { int cnt = 0; scanf("%d%d", &n, &k); for(int i = 1; i < n; i++) { int u, v; scanf("%d%d", &u, &v); E[++cnt].to = v; E[cnt].nex = head[u]; head[u] = cnt; E[++cnt].to = u; E[cnt].nex = head[v]; head[v] = cnt; } dfs(1, -1); printf("%lld ", (dp[1][k][1][1] + dp[1][k][0][1]) % mod); return 0; }