【题解】P4516 [JSOI2018] 潜入行动

【题解】P4516 [JSOI2018] 潜入行动

比较常规但是有点思维含量的一道树形 DP。

---

题目链接

P4516 [JSOI2018] 潜入行动

题意概述

给定一棵有 nn 个点的树，现在要在一些点上安装最多 kk 个监听设备，每个监听设备可以监听到与这个点直接连边的所有点，但不可以监听到它本身，现在要求每个点都被监听到，且每个点最多只能有一个监听设备，求有多少种合法的方案，答案对 1e9+7 取模。

题目分析

首先比较显然的是个树上背包。

那么按照树上背包的套路，我们定义 dpx,i 表示的是以 x 为根的子树，安装了 i 个监听设备有多少种合法的方案。

但是发现直接这样定义并不好转移，必须要考虑 x 本身是否放了监听设备以及有没有被监听。

所以我们更改一下 dp 状态：定义 dpx,i,0/1,0/1 表示的是以 x 为根的子树，安装了 i 个监听设备，x 是否安装了监听设备，x 是否被监听的方案数。

那么最后的答案就是 dp1,k,0,1+dp1,k,1,1。

树上背包的转移套路是考虑合并子树，即考虑 dpx,i+j 怎么样由 dpx,i 和 dpy,j 转移而来，其中 y 是 x 的儿子。

对于这样比较复杂的状态，我们分别考虑以 x 为根的每个状态应该怎么转移。

• 对于 dpx,i+j,0,0：

  x 没有被监听，说明 y 一定没有安装监听设备；x 没有安装设备，说明 y 一定需要被除 x 之外的其它点监听。

  转移方程：

  dpx,i+j,0,0=∑dpx,i,0,0×dpy,j,0,1

• 对于 dpx,i+j,0,1：

  x 没有安装设备，说明 y 一定被其它点监听；x 被监听了，有两种情况：

  1. x 在考虑 y 之前就已经被其它儿子监听，此时 y 之前安装不安装设备无所谓；
  2. x 在考虑 y 之前还未被其它儿子监听，所以它只能被 y 监听，即 y 必须安装设备。

  转移方程：

  dpx,i+j,0,1=∑dpx,i,0,1×(dpy,i,0,1+dpy,j,1,1)+dpx,i,0,0×dpy,j,1,1

• 对于 dpx,i+j,1,0：

  x 安装设备了，那么 y 之前是否被监听无所谓，因为反正它至少会被 x 监听；x 没有被监听，那么 y 一定不能安装设备。

  转移方程：

  dpx,i+j,1,0=∑dpx,i,1,0×(dpy,j,0,1+dpy,j,0,0)

• 对于 dpx,i+j,1,1：

  x 安装设备了，那么 y 之前是否被监听无所谓，因为反正它至少会被 x 监听；x 被监听了，有两种情况：

  1. x 在考虑 y 之前就已经被其它儿子监听，此时 y 之前安装不安装设备无所谓；
  2. x 在考虑 y 之前还未被其它儿子监听，所以她只能被 y 监听，即 y 必须安装设备。

  考虑 x 在 y 之前是否被监听时，同时考虑 y 之前是否被监听，总转移方程如下：

  dpx,i+j,1,1=∑dpx,i,1,1×(dpy,i,1,1+dpy,i,1,0+dpy,i,0,1+dpy,i,1,1)//x 之前就被监听时，y 的状态无所谓+dpx,i,1,0×(dpy,i,1,1+dpy,i,1,0)//x 之前没有被监听时，y 必须安装设备，但是否被监听无所谓

这就是全部的转移。

易错点

• 开 long long 会 MLE，请使用 unsigned int；
• 该取模的地方要取模；
• 树上背包每次转移前，先将 dpx,i,0/1,0/1 下的每一个状态都存一个临时数组下面只用临时数组转移，并将所有原 $dp_{x,i,0/1,0/1} $ 归零，防止之后的转移出现错乱。

代码实现

//luoguP4516
#include
#include
#include
#define int unsigned int
using namespace std;
const int maxn=1e5+10;
const int maxk=105;
const int mod=1e9+7;
int dp[maxn][maxk][2][2],tp[maxk][2][2];
int sz[maxn];
int n,k;
 
basic_string<int>edge[maxn];
 
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*10+ch-48;ch=getchar();}
	return x*f;
}
 
void dfs(int x,int fa)
{
	sz[x]=dp[x][0][0][0]=dp[x][1][1][0]=1;
	for(int y:edge[x])
	{
		if(y==fa)continue;
		dfs(y,x);
		for(int i=0;i<=min(sz[x],k);i++)
		{
			tp[i][0][0]=dp[x][i][0][0];
			tp[i][0][1]=dp[x][i][0][1];
			tp[i][1][0]=dp[x][i][1][0];
			tp[i][1][1]=dp[x][i][1][1];
			dp[x][i][0][0]=0;
			dp[x][i][0][1]=0;
			dp[x][i][1][0]=0;
			dp[x][i][1][1]=0;
		}
		for(int i=0;i<=min(sz[x],k);i++)
		{
			for(int j=0;j<=min(sz[y],k-i);j++)
			{
				(dp[x][i+j][0][0]+=1ll*tp[i][0][0]*dp[y][j][0][1]%mod)%=mod;
				(dp[x][i+j][0][1]+=1ll*tp[i][0][0]*dp[y][j][1][1]%mod+1ll*tp[i][0][1]*(dp[y][j][0][1]+dp[y][j][1][1])%mod)%=mod;
				(dp[x][i+j][1][0]+=1ll*tp[i][1][0]*(dp[y][j][0][0]+dp[y][j][0][1])%mod)%=mod;
				(dp[x][i+j][1][1]+=1ll*tp[i][1][0]*(dp[y][j][1][0]+dp[y][j][1][1])%mod+1ll*tp[i][1][1]*(dp[y][j][0][0]+dp[y][j][0][1]+dp[y][j][1][0]+dp[y][j][1][1])%mod)%=mod;
			}
		}
		sz[x]+=sz[y];
	}
}
 
signed main()
{
	n=read();k=read();
	for(int i=1;i
	{
		int u,v;
		u=read();v=read();
		edge[u]+=v;
		edge[v]+=u;
	}
	dfs(1,0);
	cout<<1ll*(dp[1][k][0][1]+dp[1][k][1][1])%mod<<"\n";
	return 0;
}