CF1010F Tree

有些套路，比较经典的树链剖分技巧，比较不错。

第一步，尝试弱化根节点权值 $x$ 的限制。因为题目要求 $a_u\ge \sum_v a_v$，考虑差分 $b_u=a_u-\sum_v a_v$，显然有 $b_i\ge 0，\sum_u b_i=x$。设子树大小为 $n$，我们使用隔板法即可得出答案为 $\binom{x+n-1}{n-1}$。答案只与子树大小与对应的方案数有关。

设 $f(i,j)$ 表示节点 $i$ 的子树大小为 $j$ 的方案数，暴力背包合并时间复杂度为 $\mathcal O(n^2)$。$F_i(x)$ 为其 OGF。容易得到转移 $F_i(x)=x F_L(x)F_R(x)+1$。虽然转移可以用 NTT 优化，但是由于单次转移时间复杂度为 $\mathcal O(\max(n,m)\log \max(n,m))$，复杂度反而会被卡到为 $\mathcal O(n^2\log n)$。

考虑经典优化，直接进行树链剖分。只在重链链头计算 $F_i(x)$。考虑链上如何计算，以及如何合并链之间的答案。直接不断拆开转移式子：

$$\begin{align} F_{u_1}(x)&=xF_{u_2}(x)F_{v_1}(x)+1\notag\\ &=x(xF_{u_3}(x)F_{v_2}(x)+1)F_{v_1}(x)+1\notag\\ &=x^2 F_{u_3}(x)F_{v_2}(x)F_{v_1}(x)+x F_{v_1}(x)+1\notag\\ &=\cdots\notag\\ &=\sum_{i=0}^{m-1}\prod_{j=1}^i xF_{v_j}(x) \notag\\ \end{align}$$

还是考虑分治 NTT 求，设：

$$\begin{align} G_{l,r}(x)&=\prod_{i=l}^r xF_{v_i}(x)\notag\\ H_{l,r}(x)&=\sum_{i=0}^{r-l}\prod_{j=l}^{l+i}xF_{v_j}(x) \notag\\ \end{align}$$

合并时的转移为：

$$\begin{align} G_{l,r}(x)&=G_{l,mid}(x)G_{mid+1,r}(x)\notag\\ H_{l,r}(x)&=H_{l,mid}(x)+H_{mid,r}(x)G_{l,mid}(x)\notag\\ \end{align}$$

单次分治 NTT 时间复杂度为 $\mathcal O(n\log^2 n)$。总的时间复杂度为 $\mathcal O(n\log ^3 n)$。