bzoj5314 [Jsoi2018]潜入行动树形dpDescriptionSolutionCode

122 阅读 0 评论 81 点赞

我是靠谱客的博主微笑翅膀，这篇文章主要介绍bzoj5314 [Jsoi2018]潜入行动树形dpDescriptionSolutionCode，现在分享给大家，希望可以做个参考。

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想知道，有多少种不同的放置监听设备的方法，能够使得母舰上所有
节点的通信都被监听？为了避免浪费，每个节点至多只能安装一个监听设备，且监听设备必须被用完。

1≤n≤10^5,1≤k≤min{n,100}
因为答案可能很大，你只需要输出答案mod 1,000,000,007的余数即可

Solution

点开一道水题开始修身养性，结果心态崩了

设 $f [x, k, 0 / 1, 0 / 1]$ 表示x为根的子树选了k个，x选/没选，x被覆盖/没被覆盖，转移就是size合并背包。这样做是 $O (n k)$ 的
然后要卡常，卡一卡空间。非常巧妙的地方就是我们把几个加法扔在一起膜就可以过了。。

Code

复制代码

#pragma GCC optimize(3)
#include <stdio.h>
#include <string.h>
#include <algorithm>
#include <vector>
#define rep(i,st,ed) for (register int i=st,_=ed;i<=_;++i)
#define fill(x,t) memset(x,t,sizeof(x))
#define copy(x,t) memcpy(x,t,sizeof(x))
typedef long long LL;
const int MOD=1000000007;
const int N=100005;
struct edge {int y,next;} e[N*2];
int f[N][105][2][2],g[105][2][2];
int ls[N],edCnt;
int size[N],n,m;
int read() {
int x=0,v=1; char ch=getchar();
for (;ch<'0'||ch>'9';v=(ch=='-')?(-1):(v),ch=getchar());
for (;ch<='9'&&ch>='0';x=x*10+ch-'0',ch=getchar());
return x*v;
}
void add_edge(int x,int y) {
e[++edCnt]=(edge) {y,ls[x]}; ls[x]=edCnt;
e[++edCnt]=(edge) {x,ls[y]}; ls[y]=edCnt;
}
void upd(int &x,LL y) {
x+=y; (x>=MOD)?(x-=MOD):0;
}
void dfs(int x,int fa) {
size[x]=1;
f[x][1][1][0]=f[x][0][0][0]=1;
for (int i=ls[x];i;i=e[i].next) {
int y=e[i].y;
if (y==fa) continue;
dfs(y,x);
for (register int j=0,lm=std:: min(size[x]+size[y],m);j<=lm;++j) {
copy(g[j],f[x][j]);
fill(f[x][j],0);
}
for (register int j=0,lm1=std:: min(size[x],m);j<=lm1;++j) {
for (register int k=0,lm2=std:: min(size[y],m);k<=lm2&&j+k<=m;++k) {
upd(f[x][j+k][0][0],1LL*g[j][0][0]*f[y][k][0][1]%MOD);
upd(f[x][j+k][0][1],(1LL*g[j][0][1]*(f[y][k][0][1]+f[y][k][1][1])+1LL*g[j][0][0]*f[y][k][1][1])%MOD);
upd(f[x][j+k][1][0],1LL*g[j][1][0]*(f[y][k][0][0]+f[y][k][0][1])%MOD);
upd(f[x][j+k][1][1],(1LL*g[j][1][0]*(f[y][k][1][0]+f[y][k][1][1])+1LL*g[j][1][1]*(f[y][k][0][0]+f[y][k][0][1])+1LL*g[j][1][1]*(f[y][k][1][0]+f[y][k][1][1]))%MOD);
}
}
size[x]+=size[y];
}
}
int main(void) {
freopen("data.in","r",stdin);
freopen("myp.out","w",stdout);
n=read(),m=read();
rep(i,2,n) add_edge(read(),read());
dfs(1,0);
printf("%dn", (f[1][m][0][1]+f[1][m][1][1])%MOD);
return 0;
}

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
#pragma GCC optimize(3)
#include <stdio.h>
#include <string.h>
#include <algorithm>
#include <vector>
#define rep(i,st,ed) for (register int i=st,_=ed;i<=_;++i)
#define fill(x,t) memset(x,t,sizeof(x))
#define copy(x,t) memcpy(x,t,sizeof(x))
typedef long long LL;
const int MOD=1000000007;
const int N=100005;
struct edge {int y,next;} e[N*2];
int f[N][105][2][2],g[105][2][2];
int ls[N],edCnt;
int size[N],n,m;
int read() {
int x=0,v=1; char ch=getchar();
for (;ch<'0'||ch>'9';v=(ch=='-')?(-1):(v),ch=getchar());
for (;ch<='9'&&ch>='0';x=x*10+ch-'0',ch=getchar());
return x*v;
}
void add_edge(int x,int y) {
e[++edCnt]=(edge) {y,ls[x]}; ls[x]=edCnt;
e[++edCnt]=(edge) {x,ls[y]}; ls[y]=edCnt;
}
void upd(int &x,LL y) {
x+=y; (x>=MOD)?(x-=MOD):0;
}
void dfs(int x,int fa) {
size[x]=1;
f[x][1][1][0]=f[x][0][0][0]=1;
for (int i=ls[x];i;i=e[i].next) {
int y=e[i].y;
if (y==fa) continue;
dfs(y,x);
for (register int j=0,lm=std:: min(size[x]+size[y],m);j<=lm;++j) {
copy(g[j],f[x][j]);
fill(f[x][j],0);
}
for (register int j=0,lm1=std:: min(size[x],m);j<=lm1;++j) {
for (register int k=0,lm2=std:: min(size[y],m);k<=lm2&&j+k<=m;++k) {
upd(f[x][j+k][0][0],1LL*g[j][0][0]*f[y][k][0][1]%MOD);
upd(f[x][j+k][0][1],(1LL*g[j][0][1]*(f[y][k][0][1]+f[y][k][1][1])+1LL*g[j][0][0]*f[y][k][1][1])%MOD);
upd(f[x][j+k][1][0],1LL*g[j][1][0]*(f[y][k][0][0]+f[y][k][0][1])%MOD);
upd(f[x][j+k][1][1],(1LL*g[j][1][0]*(f[y][k][1][0]+f[y][k][1][1])+1LL*g[j][1][1]*(f[y][k][0][0]+f[y][k][0][1])+1LL*g[j][1][1]*(f[y][k][1][0]+f[y][k][1][1]))%MOD);
}
}
size[x]+=size[y];
}
}
int main(void) {
freopen("data.in","r",stdin);
freopen("myp.out","w",stdout);
n=read(),m=read();
rep(i,2,n) add_edge(read(),read());
dfs(1,0);
printf("%dn", (f[1][m][0][1]+f[1][m][1][1])%MOD);
return 0;
}