BZOJ5314: [Jsoi2018]潜入行动

https://lydsy.com/JudgeOnline/problem.php?id=5314

分析:

裸树形背包，设\(f[x][i][0/1][0/1]\)表示\(x\)子树选了\(i\)个点，是否能覆盖\(x\)，是否选了\(x\)。

代码:

#include <cstdio>

#include <cstring>

#include <algorithm>

#include <cmath>

#include <cstdlib>

using namespace std;

#define N 100050

typedef long long ll;

#define mod 1000000007

int head[N],to[N<<1],nxt[N<<1],cnt,n,K,siz[N];

int f[N][105][2][2],tmp[105][2][2];

inline void add(int u,int v) {

	to[++cnt]=v; nxt[cnt]=head[u]; head[u]=cnt;

}

void upd(int &x,int y) {

	x+=y; if(x>=mod) x-=mod;

}

void dfs(int x,int y) {

	int i,j,k,p1,p2,q1,q2;

	siz[x]=1;

	f[x][0][0][0]=1;

	f[x][1][0][1]=1;

	for(i=head[x];i;i=nxt[i]) if(to[i]!=y) {

		dfs(to[i],x);

		int t=to[i];

		for(j=0;j<=siz[x]&&j<=K;j++) {

			for(p1=0;p1<2;p1++)for(q1=0;q1<2;q1++) {

				tmp[j][p1][q1]=f[x][j][p1][q1];

				f[x][j][p1][q1]=0;

			}

		}

		for(j=0;j<=siz[x]&&j<=K;j++) {

			for(k=0;k<=siz[t]&&j+k<=K;k++) {

				for(p1=0;p1<2;p1++) {

					for(q1=0;q1<2;q1++) if(tmp[j][p1][q1]) {

						for(p2=!q1;p2<2;p2++)  {

							for(q2=0;q2<2;q2++) {

								upd(f[x][j+k][p1|q2][q1],ll(tmp[j][p1][q1])*f[t][k][p2][q2]%mod);

							}

						}

					}

				}

			}

		}

		siz[x]+=siz[to[i]];

	}

}

int main() {

	scanf("%d%d",&n,&K);

	int i,x,y;

	for(i=1;i<n;i++) {

		scanf("%d%d",&x,&y);

		add(x,y); add(y,x);

	}

	dfs(1,0);

	printf("%d\n",(f[1][K][1][0]+f[1][K][1][1])%mod);

}

/*

5 3

1 2

2 3

3 4

4 5

*/