WA?
# 题面
有一棵 $n=2m$ 个点的树，树上每个节点要么是黑点要么是白点，且各有 $m$ 个。小 A 和小 B 在这棵树上进行 $m$ 轮游戏，每轮游戏，小 A 和小 B 同时在树上选择一个之前未被选择的节点，小 A 只能选白点，小 B 只能选黑点。
假如在一轮游戏中，小 A 选 $u$、小 B 选 $v$，如果 $u,v$ 之间存在祖先后代关系，则该轮游戏是“有效的”，否则为“平局”。
对于每个 $i=0\text~m$，求有多少种游戏方案使得有效的轮数等于 $i$。
两个游戏方案 $X,Y$ 不同当且仅当 $X$ 中存在一轮游戏，小 A 选了 $u$、小 B 选了 $v$，并且 $Y$ 中不存在任何一轮游戏，小 A 选了 $u$、小 B 选了 $v$。
数据规模：$1\le n\le 5000$，保证 $n$ 为偶数。
# 解析
显然要 DP……
显然直接计算恰好 $i$ 轮有效游戏的方案数特别麻烦，不妨考虑计算大于等于 $i$ 轮有效游戏的方案数。这样定义有什么好处？我们发现如果是计算恰好 $i$ 轮游戏，我们不仅要决策哪几轮游戏是有效的，还要决策那些平局是怎样进行的（要保证除了我们决策到的有效游戏，其他游戏都是平局）……这样状态就复杂了
>Tab. tly dalao 说可以定义状态 f[u][i][j] 表示 $u$ 的子树中有 $i$ 轮游戏有效、$j$ 轮游戏平局的方案数。
而改了状态定义之后，我们可以只决策哪 $i$ 轮游戏是保证有效的，其他游戏只需要把剩下的点随便两两匹配，显然有效游戏的轮数只可能更多，也就是大于等于 $i$ 轮游戏有效。这样的话，状态就可以定义为 g[u][i] 表示 $u$ 的子树中，保证了至少有 $i$ 轮游戏有效的方案数。
这就很像背包问题——其实就是树上背包。
考虑从子树 $v$ 转移到节点 $u$：
- 没有新增有效游戏：$g’_{u,i+j}\leftarrow g_{u,i}\times g_{v,j}$；
- 新增了一个有效游戏：如何能够新增？只能是 $v$ 中的一个未匹配的节点和节点 $u$ 匹配（当然 $u,v$ 颜色不同），于是开心地发现还需要再增加一维状态——
g[u][i][0/1] 最后的 0/1 表示 $u$ 现在是否已经匹配，如果没有匹配，就可以和 $v$ 中的一个未匹配的异色节点匹配。
> Hint. 可以发现在更新 $u$ 的背包时，$v$ 子树中节点 $v$ 到底有没有被选并不重要
既然更改了状态，那么重新梳理一下：
没有新增有效游戏：
$u$ 与子树 $v$ 中未匹配的异色节点匹配（$cnt$ 是 $v$ 子树中与 $u$ 异色的未匹配节点的数量，这个先维护 $v$ 中黑白节点分别的数量然后直接计算）：
这样我们可以决策出“已经进行了恰好 $i$ 轮有效游戏”的方案数 $(g_{1,i,0}+g_{1,i,1})$ ，还要把剩下的 $m-i$ 轮游戏进行完。因为状态的定义是至少 $i$ 轮，那么剩下的 $m-i$ 轮游戏到底是有效还是平局其实没有关系了，所以只需要把剩下的 $m-i$ 个黑点和 $m-i$ 个白点随意匹配即可，不难发现方案数是 $(m-i)!$，把 $(g_{1,i,0}+g_{1,i,1})\times(m-i)!$ 记作 $h_i$。
然后怎样通过 $g$ 倒回去求 $f$？显然一开始 $f_{1,m}=h_m$。不妨设我们现在已经求出了 $f_{1,i+1},f_{1,i+2},\dots,f_{1,m}$，要求 $f_{1,i}$。先给出结论：
什么意思呢？因为 $h_i$ 只是保证了已经有 $i$ 轮有效游戏，而 $f_{1,j}$ 是恰好进行了 $j$ 轮有效游戏，所以从 $f_{1,j}$ 的 $j$ 轮游戏中选出 $j$ 轮，就会被统计到 $h_i$ 中，因此 $f_{1,j}$ 对应的所有方案，在 $h_i$ 中实际上被计算了 $C_j^i$ 次。
因此
# 源代码
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
|
#include<cstdio>
#include<cstring>
#include<algorithm>
using namespace std;
const int N=5000,MOD=998244353;
int Add(int a,int b){return a+b>=MOD? a+b-MOD:a+b;}
int Sub(int a,int b){return a-b<0? a-b+MOD:a-b;}
int Mul(int a,int b){return 1ll*a*b%MOD;}
int QPow(int a,int b){
int ret=1;
while(b){
if(b&1) ret=Mul(ret,a);
a=Mul(a,a);
b>>=1;
}
return ret;
}
int n;
char sym[N+3];
int fac[N+3],inv[N+3];
int f[N+3][N+3][2],exf[N+3],cnt[N+3][2];
int tmp[N+3][2];
struct TREE{
int to[N*2+3],nxt[N*2+3],head[N+3],ncnt;
void AddEdge(int u,int v){
int p=++ncnt,q=++ncnt;
to[p]=v;nxt[p]=head[u];head[u]=p;
to[q]=u;nxt[q]=head[v];head[v]=q;
}
int operator [](int id){return head[id];}
}Tr;
int Ri(){
int a=0,c=getchar();
while(c<'0' || '9'<c) c=getchar();
while('0'<=c && c<='9'){
a=(a<<1)+(a<<3)+c-'0';
c=getchar();
}
return a;
}
void DP(int u,int fa){
cnt[u][sym[u]-'0']++;
for(int it=Tr[u];it;it=Tr.nxt[it]){
int v=Tr.to[it];
if(v==fa) continue;
DP(v,u);
cnt[u][0]+=cnt[v][0];
cnt[u][1]+=cnt[v][1];
}
int sizu=1;
f[u][0][0]=1;
for(int it=Tr[u];it;it=Tr.nxt[it]){
int v=Tr.to[it];
if(v==fa) continue;
int sizv=cnt[v][0]+cnt[v][1];
for(int i=0;i<=sizu/2;i++)
for(int j=0;j<=sizv/2;j++){
int fvj=Add(f[v][j][0],f[v][j][1]);
tmp[i+j][0]=Add(tmp[i+j][0],Mul(f[u][i][0],fvj));
tmp[i+j][1]=Add(tmp[i+j][1],Mul(f[u][i][1],fvj));
int tim=cnt[v][!(sym[u]-'0')];
tim-=j;
if(tim<0) continue;
tmp[i+j+1][1]=Add(tmp[i+j+1][1],Mul(f[u][i][0],Mul(fvj,tim)));
}
sizu+=sizv;
for(int i=0;i<=sizu/2;i++){
f[u][i][0]=tmp[i][0];
f[u][i][1]=tmp[i][1];
tmp[i][0]=tmp[i][1]=0;
}
}
}
int C(int a,int b){return Mul(fac[b],Mul(inv[a],inv[b-a]));}
int main(){
n=Ri();
fac[0]=1;
for(int i=1;i<=n;i++) fac[i]=Mul(fac[i-1],i);
inv[n]=QPow(fac[n],MOD-2);
for(int i=n-1;i>=0;i--) inv[i]=Mul(inv[i+1],i+1);
scanf("%s",sym+1);
for(int i=1;i<n;i++)
Tr.AddEdge(Ri(),Ri());
DP(1,0);
for(int i=0;i<=n/2;i++)
exf[i]=Mul(Add(f[1][i][0],f[1][i][1]),fac[n/2-i]);
for(int i=n/2;i>=0;i--){
for(int j=0;j<i;j++)
exf[j]=Sub(exf[j],Mul(exf[i],C(j,i)));
}
for(int i=0;i<=n/2;i++)
printf("%d\n",exf[i]);
return 0;
}
|
THE END
Thanks for reading!