P10013 Tree Topological Order Counting 题解

首先题目里面写了每一个数都有权值，一般这种题只能去想求出每一个的具体方案数，那么也就是我们得求出 \(h_{i,j}\) 表示在所有合法拓扑序中 \(a_i=j\) 的方案数。

一颗树的拓扑序数量是 \(\dfrac{n!}{\prod siz_i}\)，相信大家都知道。

因为我们需要保证这一棵树满足拓扑排序的条件，不难先去考虑 \(a_x=v\)，并且我们确定 \(x\) 的祖先的选数情况这时的方案数是多少。

不妨假设从 \(1\) 到 \(x\) 的数分别是 \(v_1,v_2,v_3\dots v_k\)，点分别是 \(p_1,p_2,p_3\dots p_k\)。

那么我们首先考虑 \(p_k\) 子树内选数情况是 \(\binom{n-v_k}{siz_{p_k}-1}\)，然后再去考虑 \(p_{k-1}\) 子树内选数情况，容易推出是 \(\binom{n-v_{k-1}-siz_{p_k}}{siz_{p_{k-1}}-siz_{p_k}-1}\)，以此类推，我们将这一部分的乘积叫做选数方案。

然后对于一些无关的子树直接用树的拓扑序数量把方案数算了就行。

这样我们就知道 \(a_x=v\) 并且知道 \(1 \to x\) 路径上的所有数的方案数怎么算了。

考虑 \(y\) 是 \(x\) 儿子，\(a_y=z\)，对于 \(y\) 而言，选数方案会有什么变化，你会发现 \(P_{y,z}=\dfrac{P_{x,v}}{\binom{n-v}{siz_{x}-1}}\binom{n-z}{siz_y-1}\binom{n-v-siz_y}{siz_x-siz_y-1}\)，其中 \(P_{i,j}\) 表示 \(i\) 这个点选 \(j\) 的选数方案。

上面这个式子中只和 \(x,v,y,z\) 有关系，其它的都是常量。

写出 \(P\) 的递推式子：\(P_{i,j}=\binom{n-j}{siz_i-1}\sum_{k < j} \dfrac{P_{u,k}}{\binom{n-k}{siz_u-1}}\binom{n-k-siz_i}{siz_u-siz_i-1}\)，其中 \(u\) 是 \(i\) 父亲节点。

\(ans_x=\sum P_{x,i}b_iT\)，其中 \(T\) 是无关的子树的方案数。

关于 \(P\) 的转移容易做到 \(O(1)\)，总时间复杂度 \(O(n^2)\)。