[树形dp] Luogu P4516 潜入行动

电玩女神 2021-12-03 22:51 226阅读 0赞

## 题目描述 ##

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

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

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

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

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

## 输入输出格式 ##

输入格式：

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

输出格式：

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

## 输入输出样例 ##

输入样例\#1：

5 3
    1 2
    2 3
    3 4
    4 5

输出样例\#1：

## 说明 ##

样例 1 解释

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

数据范围

存在 10\\%10% 的数据，1 \\le n \\le 201≤n≤20 ；

存在另外 10\\%10% 的数据，1 \\le n \\le 1001≤n≤100 ；

存在另外 10\\%10% 的数据，1 \\le k \\le 101≤k≤10 ；

存在另外 10\\%10% 的数据，输入的树保证是一条链；

对于所有数据，1\\le n\\le 10^51≤n≤105 ，1\\le k\\le \\min\\\{n,100\\\}1≤k≤min\{ n,100\} 。

# 题解 #

*  设 f\[i\]\[j\]\[0/1\]\[0/1\]表示i的子树中已安装j个装置， i是/否安装，是/否被控制的方案数，细节有点多，这里就不一一解释了，看代码吧

# 代码 #

1 #include <cstdio>
     2 #include <iostream>
     3 #include <cstring>
     4 using namespace std;
     5 typedef long long ll;
     6 const int mo=1e9+7,N=100010,M=110;
     7 int n,k,cnt,f[N][M][2][2],size[N],head[N];
     8 ll g[M][2][2];
     9 struct edge{ int to,from; }e[N*2];
    10 void insert(int u,int v) { e[++cnt].to=v,e[cnt].from=head[u],head[u]=cnt; }
    11 int Mo(int &a,ll b){ return (a+((int)(b%mo)))%mo; }
    12 void dfs(int u,int fa)
    13 {
    14     size[u]=1,f[u][0][0][0]=f[u][1][1][0]=1;
    15     for (int i=head[u];i;i=e[i].from)
    16     {
    17         int v=e[i].to;
    18         if (v==fa) continue;
    19         dfs(v,u);
    20         for (int i=0;i<=min(size[u],k);++i) g[i][0][0]=f[u][i][0][0],f[u][i][0][0]=0,g[i][0][1]=f[u][i][0][1],f[u][i][0][1]=0,g[i][1][0]=f[u][i][1][0],f[u][i][1][0]=0,g[i][1][1]=f[u][i][1][1],f[u][i][1][1]=0;
    21         for (int i=0;i<=min(size[u],k);++i)
    22             for (int j=0;j<=min(size[v],k-i);++j)
    23                 f[u][i+j][0][0]=Mo(f[u][i+j][0][0],(ll)g[i][0][0]*(ll)f[v][j][0][1]),
    24                 f[u][i+j][1][0]=Mo(f[u][i+j][1][0],(ll)g[i][1][0]*(ll)(f[v][j][0][0]+f[v][j][0][1])),
    25                 f[u][i+j][0][1]=Mo(f[u][i+j][0][1],(ll)g[i][0][0]*(ll)f[v][j][1][1]+(ll)g[i][0][1]*(ll)(f[v][j][0][1]+f[v][j][1][1])),
    26                 f[u][i+j][1][1]=Mo(f[u][i+j][1][1],(ll)g[i][1][0]*(ll)(f[v][j][1][1]+f[v][j][1][0])+(ll)g[i][1][1]*(ll)((ll)(f[v][j][0][0]+f[v][j][0][1])+(ll)(f[v][j][1][1]+f[v][j][1][0])));
    27         size[u]+=size[v];
    28     }
    29 }
    30 int main()
    31 {
    32     scanf("%d%d",&n,&k);
    33     for (int i=1,u,v;i<n;i++) scanf("%d%d",&u,&v),insert(u,v),insert(v,u);
    34     dfs(1,0),printf("%d\n",(f[1][k][1][1]+f[1][k][0][1])%mo);
    35 }

转载于:https://www.cnblogs.com/Comfortable/p/11205460.html