【题解】洛谷P4516（bzoj5314）[JSOI2018]潜入行动 树形DP+计数类DP

题目链接

设 $dp[u][iu][xu][yu]$dp[u][iu][xu][yu] 表示在 $u$u 的子树内选择了 $iu$iu 个节点，其中节点 $u$u 有/无被安装 $(xu=0/1)$(xu=0/1)，节点 $u$u 有无被控制 $(yu=0/1)$(yu=0/1) 的方案数。

#include<cstdio>
#include<cstring>
#include<algorithm>
using namespace std;
#define _rep(i,a,b) for(register int i=(a);i<=(b);i++)
#define _for(i,a,b) for(register int i=(a);i<(b);i++)
const int N=1e5+10,mod=1000000007;
typedef long long ll;
int n,k,tot,hd[N],sz[N],dp[N][110][2][2],pd[110][2][2],ans;
struct Edge{
	int v,nx;
}e[N<<1];
inline void sum(int&x,ll y)
{
	x=x+(y%mod);if(x>=mod)x-=mod;return;
}
void add(int u,int v)
{
	e[tot].v=v;
	e[tot].nx=hd[u];
	hd[u]=tot++;
}
void dfs(int u,int fa)
{
	sz[u]=1;dp[u][0][0][0]=1;dp[u][1][1][0]=1;
	for(int i=hd[u];~i;i=e[i].nx)
	{
		int v=e[i].v;
		if(v==fa)continue;
		dfs(v,u);
		_rep(iu,0,min(sz[u],k))_for(xu,0,2)_for(yu,0,2)pd[iu][xu][yu]=dp[u][iu][xu][yu],dp[u][iu][xu][yu]=0;
		_rep(iu,0,min(sz[u],k))_rep(iv,0,min(sz[v],k-iu))
		{
			sum(dp[u][iu+iv][0][0],(ll)pd[iu][0][0]*dp[v][iv][0][1]);
            sum(dp[u][iu+iv][0][1],(ll)pd[iu][0][1]*(dp[v][iv][0][1]+dp[v][iv][1][1])+(ll)pd[iu][0][0]*dp[v][iv][1][1]);
            sum(dp[u][iu+iv][1][0],(ll)pd[iu][1][0]*(dp[v][iv][0][0]+dp[v][iv][0][1]));
            sum(dp[u][iu+iv][1][1],(ll)pd[iu][1][1]*((ll)dp[v][iv][0][0]+dp[v][iv][0][1]+dp[v][iv][1][0]+dp[v][iv][1][1])+(ll)pd[iu][1][0]*(dp[v][iv][1][0]+dp[v][iv][1][1]));
		}
		sz[u]+=sz[v];
	}
}
int main()
{
	//freopen("in.txt","r",stdin);
    memset(hd,-1,sizeof(hd));
	scanf("%d%d",&n,&k);
    int u,v;
    _for(i,1,n)scanf("%d%d",&u,&v),add(u,v),add(v,u);
    dfs(1,0);
    printf("%d\n",(dp[1][k][0][1]+dp[1][k][1][1])%mod);
    return 0;
}

总结

（你谷讲课黑题起手）此题是一个很好的树形DP。要通过4个才能描述一个状态，然后状态转移这些才能推出来。