- 给定一棵以(1)为根的(n)个点的树（(n=2m)），其中有(m)个黑点和(m)个白点。
- 对于所有(k=1sim n)，求有多少种黑点与白点配对的方案，满足恰有(k)对是祖先-后代关系。
- (nle5 imes10^3)
树形(DP)
设(g_{x,i})表示在(x)的子树中选出(i)对祖先-后代关系的方案数。
首先，在不考虑(x)的情况下，子树之间只要做一遍树上背包就好了。
然后考虑(x)，我们可以维护出每个子树内两种颜色节点各自的数目，假设其中与(x)颜色不同的节点有(s)个。
那么要从(g_{x,i-1})转移到(g_{x,i})，就有(s-(i-1))个点与(x)颜色不同，其实这便是这个转移的系数了。
二项式反演
设(f_i)表示至少有(i)对祖先-后代关系的方案数，显然(f_i=g_{1,i} imes (m-i)!)（即钦定这(i)对，剩下的可以乱填）。
那么容易发现一个基本关系式：
[f_i=sum_{j=i}^nC_j^ians_j
]
反手一个二项式反演：
[ans_j=sum_{j=i}^n(-1)^{j-i}C_j^if_j
]
于是这题就做完了。
代码：(O(n^2))
#include<bits/stdc++.h>
#define Tp template<typename Ty>
#define Ts template<typename Ty,typename... Ar>
#define Reg register
#define RI Reg int
#define Con const
#define CI Con int&
#define I inline
#define W while
#define N 5000
#define X 998244353
#define add(x,y) (e[++ee].nxt=lnk[x],e[lnk[x]=ee].to=y)
#define C(x,y) (1LL*Fac[x]*IFac[y]%X*IFac[(x)-(y)]%X)//组合数
using namespace std;
int n,m,a[N+5],f[N+5],ee,lnk[N+5];char p[N+5];struct edge {int to,nxt;}e[N<<1];
I int QP(RI x,RI y) {RI t=1;W(y) y&1&&(t=1LL*t*x%X),x=1LL*x*x%X,y>>=1;return t;}
int Fac[N+5],IFac[N+5];I void Init_F()//预处理阶乘和阶乘逆元
{
RI i;for(Fac[0]=i=1;i<=n;++i) Fac[i]=1LL*Fac[i-1]*i%X;
for(IFac[n]=QP(Fac[n],X-2),i=n;i;--i) IFac[i-1]=1LL*IFac[i]*i%X;
}
int g[N+5][N+5],w[N+5],s[N+5][2];I void DP(CI x=1,CI lst=0)//树形DP
{
RI i,j,k;for(g[x][0]=1,i=lnk[x];i;i=e[i].nxt)//树上背包
{
if(e[i].to==lst) continue;DP(e[i].to,x);//递归
for(j=w[x];~j;--j) for(k=1;k<=w[e[i].to];++k) g[x][j+k]=(1LL*g[x][j]*g[e[i].to][k]+g[x][j+k])%X;//注意卡上界保证复杂度
s[x][0]+=s[e[i].to][0],s[x][1]+=s[e[i].to][1],w[x]+=w[e[i].to];//更新子树信息
}
for(++s[x][p[x]&1],w[x]=min(s[x][0],s[x][1]),i=w[x];~i;--i)
g[x][i]=(1LL*g[x][i-1]*(s[x][p[x]&1^1]-(i-1))+g[x][i])%X;//x的转移
}
int main()
{
RI i,j,x,y;for(scanf("%d%s",&n,p+1),m=n>>1,i=1;i^n;++i) scanf("%d%d",&x,&y),add(x,y),add(y,x);
for(Init_F(),DP(),i=0;i<=m;++i) f[i]=1LL*g[1][i]*Fac[m-i]%X;//求出f[i]
RI t=0;for(i=0;i<=m;printf("%d
",t),++i)
for(t=0,j=i;j<=m;++j) t=(1LL*((j-i)&1?X-1:1)*C(j,i)%X*f[j]+t)%X;return 0;//二项式反演
}