abc287F - Components

F - Components

一眼经典的树上背包
\(f[x][s][0/1]\)表示在x的子树中有s个连通块，选不选x的方案数
那么转移的话就是按照背包的转移即可
然后隐约记得这个是\(O(n^2)\)的
但是一直TLE，后面发现是有一个地方写法有问题，应该在计算完当前子树后再更新的size，这样可以保证复杂度。

实际跑起来会更快。

#include<algorithm>
#include<cstdio>
#include<cstring>
#include<vector>
#include<queue>
#define fo(i,a,b) for (int (i)=(a);(i)<=(b);(i)++)
#define fd(i,b,a) for (int (i)=(b);(i)>=(a);(i)--)
#define mk(x,y) make_pair((x),(y))
#define A puts("YES")
#define B puts("NO")
using namespace std;
typedef long long ll;
const int N=5005;
const ll mo=998244353;
ll f[N][N][2],g[N][N][2];
int tot,head[N],to[N*2],nex[N*2],n,sz[N];
int x,y;
void add(int x,int y){
	to[++tot]=y; nex[tot]=head[x]; head[x]=tot;
}
void ADD(ll &x,ll y){
	x=(x+y)%mo;
}
void dfs(int x,int y){
	sz[x]=1;
	g[x][1][1]=1;
	g[x][0][0]=1;
	
	for (int i=head[x];i;i=nex[i]){
		int v=to[i];
		if (v==y) continue;
		dfs(v,x);
	
		fo(k,0,sz[x]) {
			fo(s,0,sz[v]) {
				ADD(f[x][k+s][1], g[x][k][1]*f[v][s][0]%mo + g[x][k+1][1]*f[v][s][1]%mo);
				ADD(f[x][k+s][0], (f[v][s][0]+ f[v][s][1])%mo *g[x][k][0] %mo);
			}
		}
		
		sz[x]+=sz[v];
		
		fo(k,0,sz[x]) {
			g[x][k][0]=f[x][k][0];
			g[x][k][1]=f[x][k][1];
			
			f[x][k][0]=f[x][k][1]=0;
		}
	}

	fo(k,0,sz[x]) f[x][k][0]=g[x][k][0], f[x][k][1]=g[x][k][1];
	while (!f[x][sz[x]][0] && !f[x][sz[x]][1] && sz[x]) sz[x]--;
}
int main(){
	
//	freopen("data.in","r",stdin);
	scanf("%d",&n);
	fo(i,1,n-1){
		scanf("%d %d",&x,&y);
		add(x,y); add(y,x);
	}
	
	dfs(1,0);
	
	fo(i,1,n) printf("%lld\n",(f[1][i][0]+f[1][i][1])%mo);
	
	return 0;
	
}