关键词:动态规划DP   树形DP 相关题目:[JSOI2018]潜入行动

题目描述

外星人又双叒叕要攻打地球了,外星母舰已经向地球航行!这一次,JYY 已经联系好了黄金舰队,打算联合所有 JSOIer 抵御外星人的进攻。

在黄金舰队就位之前,JYY 打算事先了解外星人的进攻计划。现在,携带了监听设备的特工已经秘密潜入了外星人的母舰,准备对外星人的通信实施监听。

外星人的母舰可以看成是一棵 nn 个节点、 n1n-1 条边的无向树,树上的节点用 1,2,,n1,2,\cdots,n 编号。JYY 的特工已经装备了隐形模块,可以在外星人母舰中不受限制地活动,可以神不知鬼不觉地在节点上安装监听设备。

如果在节点 uu 上安装监听设备,则 JYY 能够监听与 uu 直接相邻所有的节点的通信。换言之,如果在节点 uu 安装监听设备,则对于树中每一条边 (u,v)(u,v) ,节点 vv 都会被监听。特别注意放置在节点 uu 的监听设备并不监听 uu 本身的通信,这是 JYY 特别为了防止外星人察觉部署的战术。

JYY 的特工一共携带了 kk 个监听设备,现在 JYY 想知道,有多少种不同的放置监听设备的方法,能够使得母舰上所有节点的通信都被监听?为了避免浪费,每个节点至多只能安装一个监听设备,且监听设备必须被用完。

输入输出格式

输入格式: 输入第一行包含两个整数 n,kn,k ,表示母舰节点的数量 nn 和监听设备的数量 kk 。 接下来 n1n-1 行,每行两个整数 u,vu,v (1u,vn)(1\le u,v\le n) ,表示树中的一条边。

输出格式: 输出一行,表示满足条件的方案数。因为答案可能很大,你只需要输出答案 modmod 1,000,000,0071,000,000,007 的余数即可。

输入输出样例

输入样例:

5 3
1 2
2 3
3 4
4 5

输出样例:

1

样例解释

样例数据是一条链 123451-2-3-4-5 。首先,节点 2244 必须放置监听设备,否则 1,51,5 将无法被监听(放置的监听设备无法监听它所在的节点)。剩下一个设备必须放置在 33 号节点以同时监听 2,42,4 。因此在 2,3,42,3,4 节点放置监听设备是唯一合法的方案。

数据范围

存在 10%10\% 的数据, 1n201 \le n \le 20 ; 存在另外 10%10\% 的数据, 1n1001 \le n \le 100 ; 存在另外 10%10\% 的数据, 1k101 \le k \le 10 ; 存在另外 10%10\% 的数据,输入的树保证是一条链; 对于所有数据, 1n1051\le n\le 10^51k1\le k\le min\min undefined n,100n,100

TeX parse error: Extra close brace or missing open brace

AC代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
#include <cstdio>
#define re register int
#define rep(i,a,b) for(re i=(a);i<=(b);++i)
#define min(a,b) ((a)<(b)?(a):(b))
const int p = 1000000007, N = 100020;
typedef long long ll;

int n, k;
int dp[N][102][2][2];
ll f[102][2][2];
int size[N];

int cnt=0, nxt[N*2], head[N], to[N*2];
inline void add(int u, int v) {
nxt[++cnt] = head[u], head[u] = cnt, to[cnt] = v;
}
#define travel(i,u) for(re i=head[u];i;i=nxt[i])

inline void dfs(int u, int fa) {
re v;
dp[u][0][0][0] = dp[u][1][0][1] = 1;
size[u] = 1;
travel(c,u) {
v = to[c];
if(v == fa) continue;
dfs(v, u);
rep(i,0,min(k, size[u]+size[v]))
rep(j,0,1)
rep(z,0,1) f[i][j][z] = 0;
rep(i,0,min(k, size[u]))
rep(j,0,min(k, size[v])) {
if(i+j > k) break;
ll t1 = dp[v][j][0][0],t2 = dp[v][j][0][1],t3 = dp[v][j][1][0],t4 = dp[v][j][1][1];
(f[i+j][0][0] += (ll)dp[u][i][0][0] * t3)%=p;
(f[i+j][0][1] += (ll)dp[u][i][0][1] * (t1+t3))%=p;
(f[i+j][1][0] += (ll)dp[u][i][1][0] * (t3+t4) + (ll)dp[u][i][0][0] * t4)%=p;
(f[i+j][1][1] += (ll)dp[u][i][1][1] * (t1+t2+t3+t4) + (ll)dp[u][i][0][1] * (t2+t4))%=p;
}
size[u] += size[v];
rep(m,0,min(k, size[u])) {
dp[u][m][0][0] = f[m][0][0];
dp[u][m][0][1] = f[m][0][1];
dp[u][m][1][0] = f[m][1][0];
dp[u][m][1][1] = f[m][1][1];
}
}
}

// dp[树根][放置个数][是否监听][是否放置]

int main() {
scanf("%d%d", &n, &k);
int u, v;
rep(i,2,n)
scanf("%d%d", &u, &v), add(u,v), add(v,u);
dfs(1,0);
printf("%d\n", (dp[1][k][1][1]+dp[1][k][1][0])%p);
}