正题

题目链接:https://www.luogu.com.cn/problem/P8352

---

题目大意

给出一棵树，每个点的权值是$[1,k]$之间的一个数，对于$i\in [1,nk]$求令这棵树的最大独立集权值为$i$的方案数。

$1\le n\le 1000,1\le k\le 5$

---

解题思路

考虑我们求最大独立集时的$dp$方程，设$f_{i,0/1}$表示$i$选/不选时的子树最大权值和。

注意到它总共有$n^2{k}^2$种状态，不能拿来dp套dp维护。

继续挖掘一下性质，若$f_{i,0}\ge f_{i,1}$，那么$f_{i,1}$显然没有用，若$f_{i,0}+k\le f_{i,1}$那么$f_{i,0}$也没有用，因为我们可以显然父节点不选择更优。

所以我们可以强制$f_{i,1}\in [f_{i,0},f_{i,0}+k]$这个范围，这样我们的状态数就只剩下$n{k}^2$种了。

设$g_{i,j,x}$表示$f_{i,0}=j,f_{i,1}=j+x$的方案数，然后$dp$子树转移即可。

时间复杂度：$O(n^2{k}^4)$

---

code

#include
#include
#include
using namespace std;
const int N=1010,P=1e9+7;
struct node{
	int to,next;
}a[N<<1];
int n,k,tot,siz[N],ls[N],ans[N*5],f[N][N*5][6],g[N*5][6];
void addl(int x,int y){
	a[++tot].to=y;
	a[tot].next=ls[x];
	ls[x]=tot;return;
}
void Add(int &x)
{x=(x>=P)?(x-P):x;}
void dfs(int x,int fa){
	siz[x]=0;
	for(int i=1;i<=k;i++)f[x][0][i]=1;
	for(int i=ls[x];i;i=a[i].next){
		int y=a[i].to;
		if(y==fa)continue;dfs(y,x);
		for(int a=0;a<=siz[x];a++){
			for(int b=0;b<=k;b++){
				if(!f[x][a][b])continue;
				for(int c=0;c<=siz[y];c++)
					for(int d=0;d<=k;d++){
						int A=a+c+d,B=a+b+c;
						B=B-A;if(B<0)B=0;
						Add(g[A][B]+=1ll*f[x][a][b]*f[y][c][d]%P);
					}
			}
		}
		siz[x]+=siz[y]+k;
		for(int a=0;a<=siz[x];a++)
			for(int b=0;b<=k;b++)
				f[x][a][b]=g[a][b],g[a][b]=0;
	}
	return;
}
int main()
{
//	printf("%d\n",sizeof(f)>>20);
//	freopen("2.in","r",stdin);
//	freopen("2.out","w",stdout);
	scanf("%d%d",&n,&k);
	for(int i=1;i<n;i++){
		int x,y;
		scanf("%d%d",&x,&y);
		addl(x,y);addl(y,x);
	}
	dfs(1,0);
	for(int a=0;a<=siz[1];a++)
		for(int b=0;b<=k;b++)
			Add(ans[a+b]+=f[1][a][b]);
	for(int i=1;i<=n*k;i++)
		printf("%d\n",ans[i]);
	return 0;
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59