bzoj 5314 [Jsoi2018]潜入行动

bzoj 5314 [Jsoi2018]潜入行动

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

Input 输入第一行包含两个整数n,k，表示母舰节点的数量n和监听设备的数量k。 接下来n-1行，每行两个整数u,v（1≤u,v≤n），表示树中的一条边。 1≤n≤10^5,1≤k≤min{n,100}

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

Sample Input 5 3 1 2 2 3 3 4 4 5 Sample Output 1 样例解释 样例数据是一条链 1–2–3–4–5 首先，节点 2和 4必须放置监听设备，否则 1,5将无法被监听（放置的监听设备无法监听它所在的节点）。剩下一 个设备必须放置在 3号节点以同时监听 2,4因此在 2,3,4节点放置监听设备是唯一合法的方案。 细节好多 无力吐槽.. 首先dp的定义也得注意细节 要不没法转移.. dp[x][i][0/1][0/1]表示 现在处于x节点已经放置i个监听 当前位置是否被监听 以及当前位置是否被子树监听 细节直接看代码吧

#include#include#include#define ll long longusing namespace std;const int mod=1e9+7;inline char gc(){ static char now[1<<16],*S,*T; if (T==S){T=(S=now)+fread(now,1,1<<16,stdin);if (T==S) return EOF;} return *S++;}inline int read(){ int x=0,f=1;char ch=gc(); while(!isdigit(ch)) {if (ch=='-') f=-1;ch=gc();} while(isdigit(ch)) x=x*10+ch-'0',ch=gc(); return x*f;}const int N=1e5+10;struct node{ int y,next;}data[N<<1];int h[N],n,k,dp[N][110][2][2],g[110][2][2],size[N],num;inline void dfs(int x,int fa){ dp[x][1][1][0]=dp[x][0][0][0]=1;size[x]=1; for (int i=h[x];i;i=data[i].next){ int y=data[i].y;if (y==fa) continue;dfs(y,x); for (int j=min(k,size[x]);~j;--j) for (int z=0;z<2;++z) for (int k1=0;k1<2;++k1) g[j][z][k1]=dp[x][j][z][k1],dp[x][j][z][k1]=0; for (int j=min(k,size[x]);~j;--j){ for (int z=min(k-j,size[y]),sum;~z;--z){ sum=((ll)dp[y][z][0][0]+dp[y][z][0][1]+dp[y][z][1][0]+dp[y][z][1][1])%mod; dp[x][z+j][0][0]=(dp[x][z+j][0][0]+(ll)g[j][0][0]*dp[y][z][0][1])%mod; dp[x][z+j][1][0]=(dp[x][z+j][1][0]+(ll)g[j][1][0]*(dp[y][z][0][1]+dp[y][z][0][0]))%mod; dp[x][z+j][0][1]=(dp[x][z+j][0][1]+(ll)dp[y][z][1][1]*(g[j][0][0]+g[j][0][1])+(ll)dp[y][z][0][1]*g[j][0][1])%mod; dp[x][z+j][1][1]=(dp[x][z+j][1][1]+(ll)g[j][1][1]*sum+(ll)g[j][1][0]*(dp[y][z][1][0]+dp[y][z][1][1]))%mod; } } size[x]+=size[y]; }}int main(){ freopen("bzoj5314.in","r",stdin); n=read();k=read(); for (int i=1;i

版权声明：本文内容由网络用户投稿，版权归原作者所有，本站不拥有其著作权，亦不承担相应法律责任。如果您发现本站中有涉嫌抄袭或描述失实的内容，请联系我们jiasou666@gmail.com 处理，核实后本网站将在24小时内删除侵权内容。