同步发表于博客园。

翻译：一棵 $n$ 个点的有根树。给定 $k,v$，求出第 $k$ 位是 $v$ 的拓扑序数量，答案对 $10^9+7$ 取模，$n\le 5000$。

设 $f_u$ 表示以 $u$ 为根的子树拓扑序数量，一遍树形 dp 易求，$dp_{u,i}$ 表示点 $u$ 在拓扑序第 $i$ 位的方案数。设 $u$ 是 $v$ 的父亲，考虑如何从 $dp_{u,*}$ 转移到 $dp_{v,*}$。

对于一个数 $i$，考虑不包含以 $v$ 为根的子树时的长度为 $n-siz_v$ 的拓扑序数 $dp'$，容易得到 $dp'_{u,i}=\frac{dp_{u,i}}{C(n-i,siz_v)f_v}$。考虑在长为 $n$ 的序列中先确定 $v$ 子树拓扑序的位置，设 $v$ 在第 $j$ 位，则其去掉第一位的拓扑序只能在长度为 $n-j$ 的后缀中放置，方案数为 $C(n-j,siz_{v}-1)$。因此我们得到 $u$ 在第 $i$ 位，$v$ 在第 $j$ 位的拓扑序数为 $dp'_{u,i}C(n-j,siz_{v}-1)f_v=dp_{u,i}\frac{C(n-j,siz_{v}-1)}{C(n-i,siz_v)}$。对 $i$ 求和可以得到：

$$ \begin{aligned} dp_{v,j}&=\sum_{i=1}^{j-1}dp_{u,i}\frac{C(n-j,siz_{v}-1)}{C(n-i,siz_v)}\\ &=C(n-j,siz_v-1)\sum_{i=1}^{j-1}\frac{dp_{u,i}}{C(n-i,siz_v)} \end{aligned} $$

发现 $\frac{dp_{u,i}}{C(n-i,siz_v)}$ 与 $j$ 无关，所以可以求出其前缀和 $pre_j=\sum_{i=1}^{j-1}\frac{dp_{u,i}}{C(n-i,siz_v)}$，得到 $dp_{v,j}=C(n-j,siz_v-1)pre_j$，于是按照这个式子 dp 可以 $O(n^2)$ 求出所有 $dp_{v,j}$，查询直接输出即可。所以本质此题可以做到多测。