洛谷 P4516 潜入行动

本文主要是介绍洛谷 P4516 潜入行动，希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！

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

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

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

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

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

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

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

5 3
1 2
2 3
3 4
4 5

输出 #1

1

说明/提示

样例 1 解释

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

代码：

#include<bits/stdc++.h>
using namespace std;
typedef long long ll;const int maxn = 1e5 + 1;
const  int mod = 1e9 + 7;
int n, k;
int dp[maxn][101][2][2];
int cnt[maxn];
int tmp[101][2][2];
vector<int> G[maxn];inline int add(ll x, ll y)
{x %= mod;y %= mod;return (int) (x+y) % mod;
}void dfs(int u,int fa){cnt[u] = dp[u][0][0][0]=dp[u][1][1][0]=1;for(int e = 0; e < G[u].size(); e++){int v=G[u][e];if(v==fa) continue;dfs(v,u);for(int i=0;i<=min(cnt[u],k);++i){tmp[i][0][0]=dp[u][i][0][0],dp[u][i][0][0]=0;tmp[i][0][1]=dp[u][i][0][1],dp[u][i][0][1]=0;tmp[i][1][0]=dp[u][i][1][0],dp[u][i][1][0]=0;tmp[i][1][1]=dp[u][i][1][1],dp[u][i][1][1]=0;}for(int i=0;i<=min(cnt[u],k);++i){for(int j=0;j<=min(cnt[v],k-i);++j){dp[u][i+j][0][0]=add((ll)dp[u][i+j][0][0],(ll)tmp[i][0][0]*(ll)dp[v][j][0][1]);dp[u][i+j][0][1]=add((ll)dp[u][i+j][0][1],(ll)tmp[i][0][0]*(ll)dp[v][j][1][1]+(ll)tmp[i][0][1]*((ll)dp[v][j][1][1]+(ll)dp[v][j][0][1]));dp[u][i+j][1][0]=add((ll)dp[u][i+j][1][0],(ll)tmp[i][1][0]*((ll)dp[v][j][0][0]+(ll)dp[v][j][0][1]));dp[u][i+j][1][1]=add((ll)dp[u][i+j][1][1],(ll)tmp[i][1][0]*((ll)dp[v][j][1][0]+(ll)dp[v][j][1][1])+(ll)tmp[i][1][1]*((ll)dp[v][j][0][0]+(ll)dp[v][j][0][1]+(ll)dp[v][j][1][0]+(ll)dp[v][j][1][1]));}}cnt[u]+=cnt[v];}
}int main()
{ios::sync_with_stdio(false);while(cin>>n>>k){int a,b;for (int i=1;i<n;i++){cin>>a>>b;G[a].push_back(b);G[b].push_back(a);}dfs(1, 0);cout << (dp[1][k][0][1] + dp[1][k][1][1]) % mod << endl;}return 0;
}

解答：

这题不会，没想出来 =_=
看洛谷上那群OI的神仙说这是个简单题，感觉很受打击，另外好久没做组合计数的题目了，也很生疏。

下面的解析主要思考为什么要设置题解中的状态。

该题目的难点在于如何设置状态，使得状态转移方程满足树形dp的性质。
假如考虑到已经知道这是一个树形dp的问题，那么子状态肯定是由子树描述。

该问题关键在于如何将子树的状态合并到根上。

假设某节点u,有n个子节点，分别为$v_1,v_2...v_n$。
假设dp(u, i)表示以u为根节点的子树放置i个设备能够覆盖节点u以及其子树全部节点的方案数。
考虑状态转移，子节点状态转移的顺序分别是$v_1,v_2...v_n$
考虑vn节点节点的合并，影响u节点是否被覆盖与$v_1,v_2...v_{n-1}$这些叶子节点中是否有放置设备的情况有关，如果这n-1个叶子节点一个放置设备的否没有，要保证u节点被覆盖，那么$v_n$节点就必须要放置设备。
但是有个问题，怎样才能知道前n-1个节点到底有没有放置设备呢？

可以考虑增加一个状态，即增加一个当前节点是否被覆盖，用来分开计数。
即设置$dp(u,i,a)$ 表示以u为根节点，安装了i个装置，且是否被覆盖。

那么状态转移可以分成如下几种情况进行合并子树：
如果u节点被覆盖，计数的过程中需要考虑两种情况，一种是$dp(u,i,1)\times dp(v,i-j,0)+dp(u,i,1)\times dp(v,i-j,1)$ 表示如果u节点被覆盖，那么子节点v的状态可以是被覆盖也可以是不被覆盖的。
此外，需要考虑如果u节点不被覆盖时转移到u节点被覆盖的情况，即$dp(u,i,0)$转移到$dp(u,i,1)$，此时需要保证当前的叶子节点v必须放置一个设备才能满足计数条件，但是状态里面没有表述，所以仅仅有三个状态还是不满足的，因此需要增加第四个状态，即该点是否放置装置。
$dp(u,i,b,a)$表示当前u放置了i个设备，该节点是否放置设备以及该节点是否被监听。
那么，状态转移的过程如下：

一下内容来自洛谷讨论区的题解

如果u没被监听，叶子节点v不能放装置，因此
$dp[u][i+j][0][0]=\sum dp[u][i][0][0]\ast dp[v][j][0][1]dp[x][i+j][0][0]$

如果u没被监听但是放了装置，u侧的状态一定是$dp[u][i][1][0]$，v是否被监听无所谓但是不能放装置，因此
$dp[u][i+j][1][0]=\sum dp[u][i][1][0]\ast (dp[v][j][0][0]+dp[v][j][0][1])$

如果u没放装置但是被监听了，这时候要分情况：

u侧的状态是$dp[u][i][0][1]$，这时候反正u已经被监听了，v放不放装置都无所谓，但是必须保证v是被监听的，所以贡献是$dp[u][i][0][1]\ast (dp[v][j][0][1]+dp[v][j][1][1])$

u侧的状态是$dp[u][i][0][0]$，这时候监听u的重任就要交给v了，同时v自己必须是被监听的，所以贡献是
$dp[u][i][0][0]\ast dp[v][j][1][1]$

因此
$dp[u][i+j][0][1]=\sum (dp[u][i][0][1]\ast (dp[v][j][0][1]+dp[v][j][1][1])+dp[u][i][0][0]\ast dp[v][j][1][1])$

如果u既放了装置又被监听，同样要分两种情况：

u侧的状态是$dp[u][i][1][0]$，需要让v来监听u，但是v是否被监听无所谓，因为u上放了装置可以保证v被监听，所以贡献是
$dp[u][i][1][0]\ast (dp[v][j][1][0]+dp[v][j][1][1])$

u侧的状态是$dp[u][i][1][1]$，这时候u的所有要求都满足了，v怎么样都行，贡献是
$dp[u][i][1][1]\ast (dp[v][j][0][0]+dp[v][j][0][1]+dp[v][j][1][0]+dp[v][j][1][1])$

因此
$dp[u][i+j][1][1]=\sum (dp[u][i][1][0]\ast (dp[v][j][1][0]+dp[v][j][1][1])+dp[u][i][1][1]\ast (dp[v][j][0][0]+dp[v][j][0][1]+dp[v][j][1][0]+dp[v][j][1][1]))$

这篇关于洛谷 P4516 潜入行动的文章就介绍到这儿，希望我们推荐的文章对编程师们有所帮助！

---