本文章由 WyOJ Shojo 从洛谷专栏拉取，原发布时间为 2024-08-22 12:58:19

P10053 [CCO2022] Bi-ing Lottery Treekets

题目考察：数论，组合数学，递推，树形 dp。
题目简述：
给定一棵有 $n$ 个结点的树，有 $k$ 个球，第 $i$ 个球将被投放在树上的 $x_i$ 号点上，但球的投放的顺序未确定，对于每次球被投放，他都会：

1. 球刚被投放：
   • 若其左右儿子均没有球，则可以向任意方向往下滚。
   • 若左儿子或右儿子上有球，则向另一方向往下滚。
   • 若左儿子和右儿子上都有球，则结束行动。
   • 若该位置有球，则该方案不合法。
2. 球是滚下来的：
   • 若其左右儿子均没有球，则向原来的方向往下滚。
   • 若左儿子或右儿子上有球，则向另一方向往下滚。
   • 若左儿子和右儿子上都有球，则结束行动。

定义 $ans_i$ 是最终落在 $i$ 号点上的球，没有则为 $0$，问最后的合法的 $ans$ 的个数对 $10^9+7$ 取模的结果。
数据范围：

• $1\le n,k\le 4000$
• $\forall i\in[1,n],1\le a_i\le n$

考虑树形 dp。

设 $f_{i,j}$ 为在 $i$ 号点上有 $j$ 个球落入了这里的合法方案数（这里的“落入”不含投放的球），那么我们枚举 $l$ 代表在投放在 $i$ 点的球中有 $l$ 个按照原来的方向往下落，这个转移方程需要含以下几部分：

• 设在 $i$ 点上投放了 $a_i$ 个球，则我们需要在其中选出 $l$ 个球，即 $\displaystyle\binom{a_i}{l}$。
• 设 $son_{i,0/1}$ 为 $i$ 点的左/右儿子，$vis=0/1$ 为他原本的方向：左/右，$b_i$ 代表在 $i$ 的子树内有多少点空着。则我们需要拿到 $vis$ 方向儿子上的方案数，则为：$f_{son_{u,vis},\min(j+l,b_{son_{u,vis}})}$，因为最多有 $\min(j+l,b_{son_{u,vis}})$ 个球按原来的方向往下落。
• 我们还需要在往这边落的 $l$ 个球中排顺序，由于它是带顺序的，所以答案是 $l^{\underline{\min(j+l,b_{son_{u,vis}})}}$。
• 我们统计右儿子的方案数的方法同上，但要注意可能有一个球停在 $i$ 点，故答案为 $f_{son_{u,[vis=0]},a_i+j-\min(j+k,b_{son_{u,vis}})-[j==b_i]}$。
• 同上，我们也要排顺序，答案是 $(a_i-l)^{\underline{a_i+j-\min(j+k,b_{son_{u,vis}})}}$。

那么我们将上面的所有数相乘累加即可。

代码