AT_agc063_e Child to Parent 题解

设 \(c_x\) 表示点 \(x\) 一共执行的操作次数，对于不同的 \(c_x\) 序列最终的 \(A\) 序列是不同的，因此我们对 \(c_x\) 序列计数即可。

容易发现一个 \(c_x\) 合法的充要是 \(0\le c_x\le A_x+R\times \sum _{v\in son(x)} c_v\)，但是我们不能把 \(c_x\) 记进状态里。

尝试设 DP \(f_x\) 表示子树 \(x\) 内的答案，假如我们求出了子树 \(x\) 内所有方案的 \(c_x\) 的和 \(g_x\)，那么容易转移出 \(f_x\)，有：

\[f_x=(A_x+1)(\prod_{v\in son(x)} f_v)+\sum _{v\in son(x)} g_v\prod _{w\in son(x)\setminus v} f_w \]

但是这个转移没有什么用，考虑设 \(f_{x,i}\) 表示子树 \(x\) 内所有方案的 \(c_x^i\) 的和，而方案数就相当于 \(f_{x,0}\)，我们的最终答案即 \(f_{1,0}\)。可以写出转移（设 \(lim=A_x+\sum c_v\)）：

\[f_{x,i}=\sum _{所有方案} \sum _{t=0}^{lim} t^i \]

用第二类斯特林数将普通幂转下降幂，得：

\[\begin{aligned} f_{x,i} &= \sum _{所有方案} \sum _{t=0}^{lim} \sum _{j=0}^{i} {i\brace j}j!\binom {t}{j} \\ &= \sum _{所有方案} \sum _{j=0}^i {i\brace j} j!\sum _{t=0}^{lim} \binom{t}{j}\\ &= \sum _{所有方案} \sum _{j=0}^{i}{i\brace j} j!\binom {lim+1}{j+1} \\ &= \sum _{所有方案} \sum _{j=0}^{i} {i\brace j} \frac{(lim+1)^{\underline{j+1}}}{j+1} \end{aligned} \]

只需求出所有方案的 \((A_x+\sum c_v)^{\underline {j+1}}\) 的和即可。转化为关于儿子的 \(f_{v,i}\) 的卷积的多项式。

复杂度是 \(O(n^3)\)。