请问为什么T了
  • 板块P1411 树
  • 楼主蒟蒻丁
  • 当前回复8
  • 已保存回复8
  • 发布时间2020/8/10 00:02
  • 上次更新2023/11/6 20:48:11
查看原帖
请问为什么T了
251882
蒟蒻丁楼主2020/8/10 00:02
void dp(int xx,int fa){
	int i,j,k;
	sz[xx]=1,f[xx][0]=f[xx][1]=1;
	for(i=head[xx];~i;i=q[i].nxt){
		int v=q[i].to;
		if(v!=fa){
			dp(v,xx);
			sz[xx]+=sz[v];
			for(j=sz[xx];j>=1;j--){
				for(k=max(0,sz[v]-sz[xx]);k<=min((S)(j-1),sz[v]);k++){
					f[xx][j]=max(f[xx][j],f[xx][j-k]*f[v][k]);
				}
			}
		}
	}
	for(i=1;i<=sz[xx];i++){
		f[xx][0]=max(f[xx][0],f[xx][i]*i);
	}
}

交换了j-k和k的位置,下面代码AC

void dp(int xx,int fa){
	int i,j,k;
	sz[xx]=1,f[xx][0]=f[xx][1]=1;
	for(i=head[xx];~i;i=q[i].nxt){
		int v=q[i].to;
		if(v!=fa){
			dp(v,xx);
			sz[xx]+=sz[v];
			for(j=sz[xx];j>=1;j--){
				for(k=min(j,sz[xx]-sz[v]);k>=max(1,j-sz[v]);k--){
					f[xx][j]=max(f[xx][j],f[xx][k]*f[v][j-k]);
				}
			}
		}
	}
	for(i=1;i<=sz[xx];i++){
		f[xx][0]=max(f[xx][0],f[xx][i]*i);
	}
}
2020/8/10 00:02
加载中...