BZOJ5314 [Jsoi2018]潜入行动 【背包类树形dp】

题目链接

BZOJ5314

题解

设\(f[i][j][0|1][0|1]\)表示\(i\)为根的子树，用了\(j\)个监测器，\(i\)节点是否被控制，\(i\)节点是否放置的方案数

然后转移即可

\(O(nk^2)\)？？

用上子树大小来优化就是\(O(nk)\)的

对于子树大小都超过\(k\)的子树，转移\(O(k^2)\)，这样的情况最多出现\(\frac{n}{k}\)次

对于子树大小有一个超过\(k\)的子树，没超过\(k\)的那个子树里每个点贡献\(O(k)\)，这样的情况对每个点最多出现一次

实现时需要诸多常数优化，才能在\(BZOJ\)上\(AC\)，洛谷上开O2随便过

#include<algorithm>

#include<iostream>

#include<cstring>

#include<cstdio>

#include<vector>

#include<cmath>

#include<map>

#define Redge(u) for (res int k = 0,to; k < ed[u].size(); k++)

#define REP(i,n) for (res int i = 1; i <= (n); i++)

#define mp(a,b) make_pair<int,int>(a,b)

#define cls(s) memset(s,0,sizeof(s))

#define cp pair<int,int>

#define LL long long int

#define res register

using namespace std;

const int maxn = 100005,maxm = 105,INF = 1000000000,P = 1000000007;

inline int read(){

	int out = 0,flag = 1; char c = getchar();

	while (c < 48 || c > 57){if (c == '-') flag = -1; c = getchar();}

	while (c >= 48 && c <= 57){out = (out << 3) + (out << 1) + c - 48; c = getchar();}

	return out * flag;

}

int n,K;

vector<int> ed[maxn];

inline void build(int u,int v){

	ed[u].push_back(v);

	ed[v].push_back(u);

}

inline void add(int& x,LL y){

	x += y; x >= P ? x -= P : 0;

}

int f[maxn][maxm][2][2],fa[maxn],siz[maxn];

LL g[maxn][2][2];

void dfs(int u){

	siz[u] = 1; f[u][0][0][0] = f[u][1][0][1] = 1;

	Redge(u) if ((to = ed[u][k]) != fa[u]){

		fa[to] = u; dfs(to);

		for (res int i = 0,lim = min(siz[u],K); i <= lim; 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;

		}

		for (res int i = 0,lim = min(siz[u],K); i <= lim; i++)

			for (res int j = 0,lim2 = min(siz[to],K); j <= lim2 && i + j <= K; j++){

				add(f[u][i + j][0][0],g[i][0][0] * f[to][j][1][0] % P);

				add(f[u][i + j][0][1],g[i][0][1] * ((f[to][j][0][0] + f[to][j][1][0])) % P);

				add(f[u][i + j][1][0],(g[i][1][0] * ((f[to][j][1][0] + f[to][j][1][1])) + g[i][0][0] * f[to][j][1][1]) % P);

				add(f[u][i + j][1][1],(g[i][1][1] * ((1ll * (f[to][j][0][0] + f[to][j][0][1]) + 1ll * (f[to][j][1][0] + f[to][j][1][1])) % P) + g[i][0][1] * (1ll * (f[to][j][0][1] + f[to][j][1][1]))) % P);

			}

		siz[u] += siz[to];

	}

}

int main(){

	n = read(); K = read();

	for (int i = 1; i < n; i++) build(read(),read());

	dfs(1);

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

	return 0;

}