深圳极速网站建设电话,手机建站程序源码,成都市做网站,个人网站首页正题
题目链接:https://www.luogu.com.cn/problem/P8352 题目大意
给出一棵树#xff0c;每个点的权值是[1,k][1,k][1,k]之间的一个数#xff0c;对于i∈[1,nk]i\in[1,nk]i∈[1,nk]求令这棵树的最大独立集权值为iii的方案数。 1≤n≤1000,1≤k≤51\leq n\leq 1000,1\leq k\…正题
题目链接:https://www.luogu.com.cn/problem/P8352 题目大意
给出一棵树每个点的权值是[1,k][1,k][1,k]之间的一个数对于i∈[1,nk]i\in[1,nk]i∈[1,nk]求令这棵树的最大独立集权值为iii的方案数。
1≤n≤1000,1≤k≤51\leq n\leq 1000,1\leq k\leq 51≤n≤1000,1≤k≤5 解题思路
考虑我们求最大独立集时的dpdpdp方程设fi,0/1f_{i,0/1}fi,0/1表示iii选/不选时的子树最大权值和。
注意到它总共有n2k2n^2k^2n2k2种状态不能拿来dp套dp维护。
继续挖掘一下性质若fi,0≥fi,1f_{i,0}\geq f_{i,1}fi,0≥fi,1那么fi,1f_{i,1}fi,1显然没有用若fi,0k≤fi,1f_{i,0}k\leq f_{i,1}fi,0k≤fi,1那么fi,0f_{i,0}fi,0也没有用因为我们可以显然父节点不选择更优。
所以我们可以强制fi,1∈[fi,0,fi,0k]f_{i,1}\in[f_{i,0},f_{i,0}k]fi,1∈[fi,0,fi,0k]这个范围这样我们的状态数就只剩下nk2nk^2nk2种了。
设gi,j,xg_{i,j,x}gi,j,x表示fi,0j,fi,1jxf_{i,0}j,f_{i,1}jxfi,0j,fi,1jx的方案数然后dpdpdp子树转移即可。
时间复杂度O(n2k4)O(n^2k^4)O(n2k4) code
#includecstdio
#includecstring
#includealgorithm
using namespace std;
const int N1010,P1e97;
struct node{int to,next;
}a[N1];
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].toy;a[tot].nextls[x];ls[x]tot;return;
}
void Add(int x)
{x(xP)?(x-P):x;}
void dfs(int x,int fa){siz[x]0;for(int i1;ik;i)f[x][0][i]1;for(int ils[x];i;ia[i].next){int ya[i].to;if(yfa)continue;dfs(y,x);for(int a0;asiz[x];a){for(int b0;bk;b){if(!f[x][a][b])continue;for(int c0;csiz[y];c)for(int d0;dk;d){int Aacd,Babc;BB-A;if(B0)B0;Add(g[A][B]1ll*f[x][a][b]*f[y][c][d]%P);}}}siz[x]siz[y]k;for(int a0;asiz[x];a)for(int b0;bk;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 i1;in;i){int x,y;scanf(%d%d,x,y);addl(x,y);addl(y,x);}dfs(1,0);for(int a0;asiz[1];a)for(int b0;bk;b)Add(ans[ab]f[1][a][b]);for(int i1;in*k;i)printf(%d\n,ans[i]);return 0;
}
