Steven_MengのBlog

传送门

考虑dp状态$dp[u][i][0/1][0/1]$表示dp到节点$u$,$u$的子树里面放了$i$个监听设备,$u$自己有没有被放,$u$自己有没有被监听。

注意到我们要满足题目的条件,所以只有u的子树内的其他点(不包含u)都被监听,才会算入dp方案数

接下来是恶心的分类讨论:

$1.dp[u][i][0][0]$,此时我们只能有一种选择,即使转移状态是$u$既不被支配,又没有放,$v$不能放,否则支配了$u$,但是$v$必须被支配($u$无法支配$v$),要不然不符合上面我们的条件。

1
Inc(dp[u][j+k][0][0],t[j][0][0]*dp[v][k][0][1]);//v一定要被支配,但是v不能放,否则支配了u

$2.dp[u][i][0][1]$

这里我们根据转移状态,再分两种情况:

$a.转移状态是dp[u][j][0][0]$:此时$v$必须放,来支配$u$,而且$v$必须被支配,因为$u$无法支配$v$。

1
Inc(dp[u][j+k][0][1],t[j][0][0]*dp[v][k][1][1]);//如果u只被支配,转移状态是u什么都不放,那么v可以既被支配又放,此时u什么都不放,也不被支配都可以

$b.转移状态是dp[u][j][0][1]$:此时$v$放不放无所谓,因为$u$已经被支配了,但是$v$必须被支配,因为$u$无法支配$v$

1
Inc(dp[u][j+k][0][1],t[j][0][1]*(dp[v][k][1][1]+dp[v][k][0][1]));//转移状态是u被支配,那么v只要被支配即可,注意到v放什么不会影响到u的状态

$3.dp[u][j][1][0]$此时转移状态只能是$u$只放而不被支配,后面$v$只要不放即可。

为什么能从$dp[v][k][0][0]$转移而来,是因为$u$放了,可以支配$v$,满足上面的条件。

1
Inc(dp[u][j+k][1][0],t[j][1][0]*(dp[v][k][0][0]+dp[v][k][0][1]));//如果u只被放,转移状态只能是u只被放,所以v不能放,有两种情况

$4.dp[u][j][1][1]$

这里我们根据转移状态,再分两种情况:

$a.转移状态是dp[u][j][1][1]$此时随便乱搞,其他四种情况都是合法的。

1
Inc(dp[u][j+k][1][1],t[j][1][1]*(dp[v][k][0][0]+dp[v][k][0][1]+dp[v][k][1][0]+dp[v][k][1][1]));//如果u既被支配又被放,转移状态是u既被支配又被放,那么剩下随便乱搞

$a.转移状态时dp[u][j][1][0]$此时$v$只要能够支配$u$即可,所以$v$要放。

1
Inc(dp[u][j+k][1][1],t[j][1][0]*(dp[v][k][1][1]+dp[v][k][1][0]));//转移状态是u只被放,那v必须放,来支配u,注意到v可以不被支配,因为u放了

注意到$dp$过程无法改变$u$节点有没有放的事实,即$dp[][][0][0/1]$只能从$dp[][][0][0/1]$转移而来,同理$dp[][][1][0/1]$只能从$dp[][][1][0/1]$转移而来。

注意此题卡内存,以下代码会MLE。(防抄袭)

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
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
#include <bits/stdc++.h>
#define MOD 1000000007
#define MAXN 100005
#define MAXK 105
#define int long long
using namespace std;
inline int read(){
int x=0,f=1;
char ch=getchar();
while (ch<'0'||ch>'9'){
if (ch=='-') f=-1;
ch=getchar();
}
while (ch>='0'&&ch<='9'){
x=(x<<3)+(x<<1)+(ch^'0');
ch=getchar();
}
return x*f;
}
vector<int>G[MAXN];
inline void AddEdge(int u,int v){
G[u].push_back(v);
}
int dp[MAXN][MAXK][2][2],t[MAXK][2][2],sz[MAXN],m;
#define Set(x,y) t[j][x][y]=dp[u][j][x][y];dp[u][j][x][y]=0
inline void Inc(int &a,int b){
a=(a+b)%MOD;
}
void dfs(int u,int father){
sz[u]=1;
dp[u][1][1][0]=dp[u][0][0][0]=1;
for (register int i=0;i<G[u].size();++i){
int v=G[u][i];
if (v==father) continue;
dfs(v,u);
int Max1=min(m,sz[u]),Max2=min(m,sz[v]);
for (register int j=0;j<=Max1;++j){
Set(0,0);
Set(0,1);
Set(1,0);
Set(1,1);
}
for (register int j=0;j<=Max1;++j){
for (register int k=0;k<=Max2;++k){
if (j+k>m) continue;
//printf("In");
Inc(dp[u][j+k][0][0],t[j][0][0]*dp[v][k][0][1]);//v一定要被支配,但是v不能放,否则支配了u

Inc(dp[u][j+k][0][1],t[j][0][0]*dp[v][k][1][1]);//如果u只被支配,转移状态是u什么都不放,那么v可以既被支配又放,此时u什么都不放,也不被支配都可以
Inc(dp[u][j+k][0][1],t[j][0][1]*(dp[v][k][1][1]+dp[v][k][0][1]));//转移状态是u被支配,那么v只要被支配即可,注意到v放什么不会影响到u的状态

Inc(dp[u][j+k][1][0],t[j][1][0]*(dp[v][k][0][0]+dp[v][k][0][1]));//如果u只被放,转移状态只能是u只被放,所以v不能放,有两种情况

Inc(dp[u][j+k][1][1],t[j][1][1]*(dp[v][k][0][0]+dp[v][k][0][1]+dp[v][k][1][0]+dp[v][k][1][1]));//如果u既被支配又被放,转移状态是u既被支配又被放,那么剩下随便乱搞
Inc(dp[u][j+k][1][1],t[j][1][0]*(dp[v][k][1][1]+dp[v][k][1][0]));//转移状态是u只被放,那v必须放,来支配u,注意到v可以不被支配,因为u放了

//注意到dp过程无法改变u节点有没有放的事实,即dp[][][0][0/1]只能从dp[][][0][0/1]转移而来,同理dp[][][1][0/1]只能从dp[][][1][0/1]转移而来
}
}
sz[u]+=sz[v];
}
}
#undef int
int main(){
#define int long long
int n=read();m=read();
for (register int i=1;i<n;++i){
int u=read(),v=read();
AddEdge(u,v);
AddEdge(v,u);
}
dfs(1,1);
printf("%lld\n",(dp[1][m][0][1]+dp[1][m][1][1])%MOD);//1一定被支配
}

 评论