题目
思路
非平局回合数\(k\)是不好求的，我们考虑先求钦定非平局回合数为\(k\)的数量。
这可以直接树形 dp，设 \(dp_{u,j}\)表示\(u\)为根节点钦定非平局回合数\(k\)的数量。
转移很简单直接树上背包即可，时间复杂度\(O(N^2)\)。
时间复杂度证明
求出了 dp 后，设\(f_{i}\)为钦定非平局回合数\(k\)的总数量。
那么有\(f_{i}=dp_{1,i} \times (n-i)!\)(1为根节点)。
接下来直接二项式反演即可。
设\(g_{i}\)表示非平局回合数恰好为\(k\)的数量。
那么有\(f_{i}= \sum_{j=k}^{n} \binom{j}{k} \times g_{j}\)。
则\(g_{i}=\sum_{j=k}^{n} -1^{n-j} \times \binom{j}{k} \times f_{j}\)。
证明
\(g_{i}=\sum_{j=k}^{n} -1^{i-j} \times \binom{j}{k} \times f_{j}\)
\(g_{i}=\sum_{j=k}^{n} -1^{i-j} \times \binom{j}{k} \times \sum_{z=j}^{i} \binom{z}{j} \times g_{z}\)
\(g_{i}=\sum_{j=k}^{n} -1^{i-j} \times \sum_{z=k}^{i} \binom{z}{j} \times \binom{j}{k} \times g_{z}\)
\(g_{i}=\sum_{j=k}^{n} -1^{i-j} \times \sum_{z=k}^{i} \binom{z}{k} \times \binom{z-k}{j-k} \times g_{z}\)
\(g_{i}=\sum_{z=k}^{n} \binom{z}{k} \times g_{z} \times \sum_{j=k}^{i} \binom{z-k}{j-k} \times -1^{i-j}\)
最后时间复杂度\(O(N^2)\)。
code
#include <bits/stdc++.h>
using namespace std;
using ll = long long;
#define rep(i,l,r) for(int i=(l);i<=(r);++i)
#define per(i,r,l) for(int i=(r);i>=(l);--i)const int N=5005,mod=998244353;
ll fac[N],inv[N];
ll pom(ll x,ll y,ll p){ll res=1;for(;y;y>>=1,x=x*x%p) if(y&1) res=res*x%p;return res;}
ll C(ll n,ll m){return (m<0||n<m)?0ll:fac[n]*inv[n-m]%mod*inv[m]%mod;}int n,u,v,cnt[2][N];
bool p[N];
char c;
vector<int>ve[N];
ll dp[N][N],a[N<<1];
void add(ll &x,ll y){x+=y;if(x>=mod||x<=-mod) x%=mod;if(x<0) x+=mod;}
void dfs(int u,int fa){dp[u][0]=1;for(auto v:ve[u]){if(v==fa) continue;dfs(v,u);int cu=cnt[0][u]+cnt[1][u],cv=cnt[0][v]+cnt[1][v];rep(i,0,cu+cv) a[i]=0;rep(i,0,min(cu,n)) rep(j,0,min(cv,n-i)) add(a[i+j],dp[u][i]*dp[v][j]);rep(i,0,cu+cv) dp[u][i]=a[i]; cnt[0][u]+=cnt[0][v];cnt[1][u]+=cnt[1][v];}per(i,min(cnt[0][u],cnt[1][u]),1) add(dp[u][i],dp[u][i-1]*(cnt[p[u]^1][u]-(i-1)));
}
ll f[N],g[N];
void solve(){cin>>n;auto ad=[](int u,int v){ve[u].push_back(v),ve[v].push_back(u);};rep(i,1,n) cin>>c,cnt[p[i]=(c=='1')][i]=1;rep(i,1,n-1) cin>>u>>v,ad(u,v);n>>=1;dfs(1,0);rep(i,0,n) f[i]=dp[1][i]*fac[n-i]%mod;rep(k,0,n) {ll ans=0,op=1;rep(i,k,n) add(ans,C(i,k)*f[i]*op),op*=-1;cout<<ans<<'\n';}
}
int main(){fac[0]=1;for(int i=1;i<N;++i) fac[i]=fac[i-1]*i%mod;inv[N-1]=pom(fac[N-1],mod-2,mod);for(int i=N-2;i>=0;--i) inv[i]=inv[i+1]*(i+1)%mod;solve();return 0;
}