[JSOI2018]潜入行动

题目

我好菜啊，嘤嘤嘤

原来本地访问数组负下标不会报\(RE\)或者\(WA\)，甚至能跑出正解啊

这道题还是非常呆的

我们发现\(k\)很小，于是断定这是一个树上背包

发现在一个点上安装控制器并不能控制这个点，可能需要到父亲那边才能控制这个点，于是我们设\(dp[i][j][0/1][0/1]\)表示在以\(i\)为根的子树里放置了\(j\)个监视器，控制了除了点\(i\)以外的点，在\(i\)点装没装控制器，\(i\)点有没有被控制

大力分类套论几个转移

\(dp[i][j][0][0]\)因为没有放监视器，必须要求其儿子们在他们的子树内部就被监视了，同时因为\(i\)还没有被监视，于是儿子不能放监视器，于是从\([0][1]\)转移

\(dp[i][j][1][0]\)因为放了监视器，能监视儿子，于是儿子们有没有被监视都可以，但是都不能放监视器，于是从\([0][1]\)和\([0][0]\)转移

\(dp[i][j][0][1]\)因为没有放监视器，儿子们必须全部被监视到从\([0][1]\)转移，因为\(i\)被监视，所以至少得有一个儿子放监视器，所以至少一个从\([1][1]\)转移

\(dp[i][j][1][1]\)放了监视器，而要求被监视，从四种状态都能转移，但是要求至少有一个转移是\([1][0]\)或\([1][1]\)（放了监视器）

直接树形背包转移，之后大力容斥掉没有选择那个至少要选择的情况就好了

发现\(dp[i][j][0][1]\)要减掉的正好是\(dp[i][j][0][0]\)，\(dp[i][j][1][1]\)要减掉的正好是\(dp[i][j][1][0]\)

代码

#include<algorithm>

#include<iostream>

#include<cstring>

#include<cstdio>

#define re register

#define LL long long

#define max(a,b) ((a)>(b)?(a):(b))

#define min(a,b) ((a)<(b)?(a):(b))

const int maxn=1e5+5;

const int mod=1e9+7;

inline int read() {

	char c=getchar();int x=0;while(c<'0'||c>'9') c=getchar();

	while(c>='0'&&c<='9') x=(x<<3)+(x<<1)+c-48,c=getchar();return x;

}

struct E{int v,nxt;}e[maxn<<1];

int head[maxn],sum[maxn];

int dp[maxn][105][2][2];

int f[105][2][2];

int n,m,num;

inline void add(int x,int y) {e[++num].v=y;e[num].nxt=head[x];head[x]=num;}

inline int qm(int a) {return a>mod?a-mod:a;}

void dfs(int x,int fa) {

	int cur=0;

	sum[x]=1;

	for(re int i=head[x];i;i=e[i].nxt) {

		if(e[i].v==fa) continue;

		int v=e[i].v;

		dfs(v,x);cur++;

		sum[x]+=sum[v];

		int U=min(sum[x],m);

		if(cur==1) {

			for(re int k=0;k<=min(sum[v],m);k++) {

				dp[x][k][0][0]=dp[v][k][0][1];

				dp[x][k+1][1][0]=qm(dp[v][k][0][1]+dp[v][k][0][0]);

				dp[x][k+1][1][1]=(dp[v][k][1][1]+dp[v][k][1][0])%mod+(dp[v][k][0][0]+dp[v][k][0][1])%mod;

				dp[x][k+1][1][1]%=mod;

				dp[x][k][0][1]=qm(dp[v][k][1][1]+dp[v][k][0][1]);

			}

			continue;

		}

		for(re int j=U;j>=0;--j) {

			f[j][0][0]=dp[x][j][0][0],dp[x][j][0][0]=0;

			f[j][0][1]=dp[x][j][0][1],dp[x][j][0][1]=0;

			f[j][1][0]=dp[x][j][1][0],dp[x][j][1][0]=0;

			f[j][1][1]=dp[x][j][1][1],dp[x][j][1][1]=0;

		}

		for(re int j=U;j>=0;--j)

			for(re int k=0;k<=min(sum[v],m);k++) {

				int t=j-k;

				if(t<0) continue;

				dp[x][j][0][0]=(dp[x][j][0][0]+1ll*f[t][0][0]*dp[v][k][0][1]%mod)%mod;

				dp[x][j][1][0]=(dp[x][j][1][0]+1ll*f[t][1][0]*qm(dp[v][k][0][1]+dp[v][k][0][0])%mod)%mod;

				dp[x][j][0][1]=(dp[x][j][0][1]+1ll*f[t][0][1]*qm(dp[v][k][1][1]+dp[v][k][0][1])%mod)%mod;

				dp[x][j][1][1]=(dp[x][j][1][1]+1ll*f[t][1][1]*qm(qm(dp[v][k][1][1]+dp[v][k][1][0])+qm(dp[v][k][0][0]+dp[v][k][0][1]))%mod)%mod;

			}

	}

	if(!cur) {dp[x][0][0][0]=dp[x][1][1][0]=1;return;}

	for(re int j=0;j<=min(sum[x],m);j++)

		dp[x][j][0][1]=(dp[x][j][0][1]-dp[x][j][0][0]+mod)%mod,

		dp[x][j][1][1]=(dp[x][j][1][1]-dp[x][j][1][0]+mod)%mod;

}

int main() {

	n=read();m=read();

	for(re int x,y,i=1;i<n;i++)

		x=read(),y=read(),add(x,y),add(y,x);

	dfs(1,0);

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

	return 0;

}