题目链接：https://www.luogu.com.cn/problem/P6478
解题思路完全来自 GaryH大佬的博客
注意：
由于 \(f_{1, i}\) 表示钦定了 \(i\) 对，但是剩余的 \(\frac{n}{2} - i\) 对可以任意组合，所以
\(f_{1, i}\) 还得乘上 \((\frac{n}{2} - i)!\)。
示例程序：
#include <bits/stdc++.h>
using namespace std;
const long long mod = 998244353;
const int maxn = 5005;void add(long long &a, long long b) {a = (a + b % mod + mod) % mod;
}int n, c[maxn], sz[maxn][2], mx[maxn]; // mx[u] : 最多能匹配多少对
long long f[maxn][maxn/2], tmp[maxn], fac[maxn] = { 1 };
char s[maxn];
vector<int> g[maxn];struct Binom {int c[maxn/2][maxn/2];void init() {for (int i = 0; i <= n/2; i++) {for (int j = 0; j <= i; j++) {if (j == 0 || j == i)c[i][j] = 1;elsec[i][j] = (c[i-1][j-1] + c[i-1][j]) % mod;}}}} binom;void dfs(int u, int p) {sz[u][ c[u] ] = 1;f[u][0] = 1;for (auto v : g[u]) {if (v != p) {dfs(v, u);int num1 = mx[u], num2 = mx[v];fill(tmp, tmp+num1+num2+2, 0);for (int i = 0; i <= num1; i++)for (int j = 0; j <= num2; j++)add(tmp[i+j], f[u][i] * f[v][j]);copy(tmp, tmp+num1+num2+2, f[u]);sz[u][0] += sz[v][0];sz[u][1] += sz[v][1];mx[u] += mx[v];}}for (int i = mx[u] + 1; i > 0; i--) {int cnt = sz[u][ 1 - c[u] ] - (i - 1);if (cnt > 0) {add(f[u][i], f[u][i-1] * cnt);if (i == mx[u] + 1 && f[u][i])mx[u]++;}}}int main() {scanf("%d%s", &n, s+1);binom.init();for (int i = 1; i <= n/2; i++)fac[i] = fac[i-1] * i % mod;for (int i = 1; i <= n; i++)c[i] = s[i] - '0';for (int i = 1, u, v; i < n; i++) {scanf("%d%d", &u, &v);g[u].push_back(v);g[v].push_back(u);}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++) {long long ans = 0;for (int i = k, flag = 1; i <= n/2; i++, flag = -flag) {long long tmp = binom.c[i][k] * f[1][i] % mod;add(ans, flag * tmp);}printf("%lld\n", ans);}return 0;
}