CF995F Cowmpany Cowmpensation

给定一棵以 \(1\) 为根的 \(n\) 个节点的树，第 \(i\) 个点的父亲为 \(p_i\)。你需要给第 \(i\) 个节点赋予一个整数点权 \(a_i\)，需要满足下面的性质：

• \(\forall i \in [1,n],a_i \in [1,D]\)。

• \(\forall i \in [2,n],a_i \leq a_{p_i}\)。

求不同方案的总数。

\(1 \leq n \leq 3000\)，\(1 \leq D \leq 10^9\)。

考虑朴素 dp，记 \(dp_{i,j}\) 表示在以 \(i\) 为根的子树中 \(a_i \leq j\) 的填法总数，可得：

\[dp_{i,j}=dp_{i,j-1}+\prod\limits_{k \in son_i} dp_{k,j} \]

考虑到若 \(i\) 为原树的叶子节点，则 \(dp_{i,j}=j\)，易知 \(dp_i\) 为关于 \(j\) 的一次多项式。由于 \(dp_{i,j}\) 为所有儿子的 \(dp_{i,j}\) 乘积的前缀和，容易发现 \(dp_{i}\) 应该是 \(k\) 次多项式，其中 \(k\) 为 \(i\) 的子树大小，于是你算出 \(O(n)\) 个 \(dp_{1,j}\) 的值后插值即可得到 \(dp_{1,D}\)。时间复杂度 \(O(n^2)\)。