https://www.luogu.com.cn/problem/P6478
二项式反演
发现恰好有(k)个非平局的回合数，“恰好”这并不好做，这里套路地设(f_i)表示恰好有(i)个非平局的方案数，(g_i)表示“钦定”了(i)个非平局的然后剩下的(m-i)个回合两人随便选点的方案数。
考虑(f)和(g)有什么关系，对于(g_k)与(f_i)（(i ge k)），由于是先钦定(k)局，考虑(i)局中钦定了哪(k)局，换句话说(f_i)在(g_k)中会被重复计数(inom{i}{k})次
于是
由二项式反演可得
于是算出(g)后我们就可以(O(m^2))得到答案了。
考虑树形dp，令(dp(u,i))表示点(u)的子树内，选出(i)组有祖孙关系的点对的方案数。
只有两种情况
-
- 不选(u)节点
-
- 选(u)节点
先来看(1)，不选(u)节点的话就类似树上背包那样合并儿子们的信息
这样我们得到了新的(dp(u,i))。
然后如果选择了点(u)，那么加入这个点对过后会让(dp(u,i))对(dp(u,i+1))做出贡献（这里的(dp)值都是上面更新好的），具体的会使得(dp(u,i+1))加上(dp(u,i) imes u)子树内的剩下没有被选的点（对手的点）的个数，剩下的点的个数就是(u)子树内对手点的个数(-i)。
注意上面这个东西不要在更新的时候覆盖(dp)值（可以倒序枚举(i)或者再开一个数组）
然后显然(g_k=dp(1,k) imes (m-k)!)（即钦定(k)组的方案数乘上剩下随便选的方案数）
这样背包貌似是(O(n^3))的...
但对于(dp(u,i))，粗略的估计一下(i)的上界就是(siz_u)。
然后按这个上界枚举的话复杂度会到(O(n^2))。
感性的理解就是两个点(u,v)仅会在(lca(u,v))处对复杂度造成贡献。
(Code:)
#include <bits/stdc++.h>
using namespace std;
#define maxn 5000
#define N 5555
#define MOD 998244353
inline int qpow(int a,int b=MOD-2,int m=MOD)
{
int ans=1%m;
for(;b;b>>=1,a=1ll*a*a%m)
if(b&1) ans=1ll*ans*a%m;
return ans;
}
inline char nc()
{
char ch=getchar(); while(isspace(ch))ch=getchar();
return ch;
}
int fac[N],ifac[N];
inline int comb(int n,int r)
{return 1ll*fac[n]*ifac[r]%MOD*ifac[n-r]%MOD;}
bool bl[N]; int n,m;
int fst[N<<1],nxt[N<<1],to[N<<1],ec;
void ade(int u,int v) {to[++ec]=v,nxt[ec]=fst[u],fst[u]=ec;}
void addedge(int u,int v) {ade(u,v),ade(v,u);}
#define fedge(i,u) for (int i=fst[u],v=to[i];i;i=nxt[i],v=to[i])
int siz[N],c[2][N],f[N][N],df[N];
void dfs(int u,int ff)
{
f[u][0]=1,siz[u]=1,c[0][u]=bl[u]==0,c[1][u]=bl[u]==1;
fedge(_,u) if(v!=ff)
{
dfs(v,u);
for(int i=0;i<=siz[u];i++)
for(int j=0;j<=siz[v];j++)
{
df[i+j]+=1ll*f[u][i]*f[v][j]%MOD;
if(df[i+j]>=MOD) df[i+j]-=MOD;
}
siz[u]+=siz[v];
c[0][u]+=c[0][v],c[1][u]+=c[1][v];
for(int i=0;i<=siz[u];i++) f[u][i]=df[i];
for(int i=0;i<=siz[u];i++) df[i]=0;
}
int cc=c[!bl[u]][u];
for(int i=0;i<=cc;i++)
{
df[i+1]+=1ll*f[u][i]*(cc-i)%MOD;
if(df[i+1]>=MOD) df[i+1]-=MOD;
}
for(int i=0;i<=siz[u];i++) {f[u][i]+=df[i]; if(f[u][i]>=MOD)f[u][i]-=MOD;}
for(int i=0;i<=cc;i++) df[i]=df[i+1]=0;
}
int ans[N];
int main()
{
fac[0]=ifac[0]=1;
for(int i=1;i<=maxn;i++) fac[i]=1ll*fac[i-1]*i%MOD,ifac[i]=qpow(fac[i]);
scanf("%d",&n),m=n>>1;
for(int i=1;i<=n;i++) bl[i]=nc()=='1';
for(int u,v,i=1;i<n;i++)
scanf("%d%d",&u,&v),addedge(u,v);
dfs(1,0);
for(int i=0;i<=m;i++)
{
ans[i]=0;
for(int j=i;j<=m;j++)
{
ans[i]+=1ll*comb(j,i)*(((j-i)&1)?MOD-1:1)%MOD*f[1][j]%MOD*fac[m-j]%MOD;
if(ans[i]>=MOD) ans[i]-=MOD;
}
printf("%d
",ans[i]);
}
return 0;
}