记录编号	597648	评测结果	AAAAAAAAAAAAAAAAAAAA
题目名称	[NOI Online 2020 2nd]游戏(民间数据)	最终得分	100
用户昵称	┭┮﹏┭┮	是否通过	通过
代码语言	C++	运行时间	0.749 s
提交时间	2024-12-09 22:01:18	内存使用	17.43 MiB

#include <bits/stdc++.h>
using namespace std;
#define ll long long
#define pii pair<int,ll>
#define fi first
#define in inline
#define se second
#define mp make_pair
#define pb push_back
const int N = 5010;
const ll mod = 998244353;

ll read(){
	ll x = 0,f = 1;char c = getchar();
	for(;c < '0' || c > '9';c = getchar())if(c == '-')f = -1;
	for(;c >= '0' && c <= '9';c = getchar())x = (x<<1) + (x<<3) + c-'0';
	return x * f;
}

int n;
char c[N];
vector<int>e[N];
int a[N],s[2][N];
ll f[N][N],fac[N],inv[N],g[N];
ll C(ll n,ll m){
	if(n < 0 || m < 0 || n - m < 0)return 0;
	return fac[n] * inv[m] % mod * inv[n - m] % mod;
}
ll ksm(ll x,ll y){
	ll ans = 1;
	while(y){
		if(y & 1)ans = ans * x % mod;
		x = x * x % mod,y >>= 1;
	}return ans;
}
void dfs(int x,int fa){
	f[x][0] = 1;
	for(int y : e[x]){
		if(y == fa)continue;
		dfs(y,x);
		//O(n^2) 背包 
		for(int i = 0;i <= min(s[0][x] + s[1][x] + s[0][y] + s[1][y],n / 2);i++)g[i] = 0;
		for(int j = 0;j <= min(n / 2,s[0][x] + s[1][x]);j++)
			for(int k = 0;k <= min(n / 2 - j,s[0][y] + s[1][y]);k++)
				(g[j + k] += f[x][j] * f[y][k]) %= mod;
		for(int i = 0;i <= min(s[0][x] + s[1][x] + s[0][y] + s[1][y],n / 2);i++)f[x][i] = g[i];
		
		s[0][x] += s[0][y],s[1][x] += s[1][y];
	}
	for(int i = min(s[0][x] + s[1][x],n / 2);i >= 1;i--)
		if(s[a[x] ^ 1][x] - i + 1 >= 0)(f[x][i] += f[x][i - 1] * (s[a[x] ^ 1][x] - i + 1) % mod) %= mod;
}

int main(){
	freopen("noi_online2020_match.in","r",stdin);
	freopen("noi_online2020_match.out","w",stdout);
	n = read();
	fac[0] = inv[0] = 1;
	for(int i = 1;i <= n;i++)fac[i] = fac[i - 1] * i % mod;
	inv[n] = ksm(fac[n],mod - 2);
	for(int i = n - 1;i >= 1;i--)inv[i] = inv[i + 1] * (i + 1) % mod;
	scanf("%s",c + 1);
	for(int i = 1;i <= n;i++)a[i] = c[i] - '0',s[c[i] - '0'][i]++;
	for(int i = 1;i < n;i++){
		int x = read(),y = read();
		e[x].pb(y),e[y].pb(x);
	}
	dfs(1,0);  
	for(int i = 0;i <= n / 2;i++)f[1][i] = f[1][i] * fac[n / 2 - i] % mod;
	for(int k = 0;k <= n / 2;k++){
		ll ans = 0;
		for(int i = k;i <= n / 2;i++)(ans += C(i,k) * (((i - k) & 1) ? mod - 1 : 1) % mod * f[1][i] % mod) %= mod;
		printf("%lld\n",ans);
	}

	return 0;

}