先从最朴素的 DP 出发。

设 $f_n$ 表示恰有 $n$ 个叶子的所有合法二叉树的美观度之和。

再定义权值函数

$$w(x)= \begin{cases} v_i,& x=s_i,\\ A,& \text{否则。} \end{cases}$$

那么一棵有 $n$ 个叶子的树，根节点的左子树可以有 $j$ 个叶子，右子树有 $n-j$ 个叶子，其中 $1 \le j \le n-1$。

根节点的贡献是 $w(j)$，左右子树的贡献分别是 $f_j,f_{n-j}$，于是有

$$f_1=1,$$ $$f_n=\sum_{j=1}^{n-1} w(j)f_jf_{n-j}\qquad (n\ge 2)。$$

这就是最直接的做法。时间复杂度 $O(n^2)$，可以通过小数据。

---

先拆掉“默认值 $A$”

这题的关键在于：真正特殊的位置只有 $k \le 10$ 个。

令

$$b_x=w(x)-A。$$

于是只有当 $x=s_i$ 时，$b_x \ne 0$；其余位置 $b_x=0$。

转移式可以写成

$$f_n=A\sum_{j=1}^{n-1}f_jf_{n-j}+\sum_{j=1}^{n-1}b_jf_jf_{n-j}。$$

第二项只有很少几个位置有贡献，这是后面优化的突破口。

如果 $A=0$，那么第一项直接消失，只剩下特殊位置转移：

$$f_n=\sum_{j=1}^{n-1}b_jf_jf_{n-j}。$$

由于非零的 $b_j$ 只有 $k$ 个，所以直接枚举这些位置即可，复杂度 $O(nk)$。

下面只讨论 $A \ne 0$ 的情况。

---

生成函数

定义生成函数

$$F(x)=\sum_{n\ge 1} f_n x^n。$$

再定义

$$P(x)=\sum_{n\ge 1} b_n f_n x^n。$$

注意到 $P(x)$ 只有至多 $k$ 个非零项，因为只有 $n=s_i$ 时 $b_n$ 才非零。

由递推式直接得到

$$F(x)=x+A F(x)^2+P(x)F(x)。$$

整理一下：

$$A F(x)^2-(1-P(x))F(x)+x=0。$$

这是一个关于 $F(x)$ 的二次方程。仿照求 Catalan 生成函数的写法，设

$$S(x)=1-P(x)-2AF(x)。$$

那么有

$$S(x)^2=(1-P(x))^2-4Ax。$$

记

$$D(x)=(1-P(x))^2-4Ax。$$

于是

$$S(x)^2=D(x)。$$

现在问题就变成：已知一个非常稀疏的多项式 $D(x)$（系数非 $0$ 的项只有 $O(k^2)$ 个），要求出它的平方根 $S(x)$ 的各项系数。

---

从 $S(x)^2=D(x)$ 推系数递推

设

$$S(x)=1+\sum_{n\ge 1}s_n x^n, \qquad D(x)=1+\sum_{n\ge 1}d_n x^n。$$

直接平方比较系数会得到一个卷积，还是太慢。这里用一个常见技巧：对

$$S(x)^2=D(x)$$

两边求导，得到

$$2S(x)S'(x)=D'(x)。$$

再乘上 $S(x)$，整理为

$$2D(x)S'(x)=D'(x)S(x)。$$

比较 $x^{n-1}$ 的系数，可以得到

$$2n\,s_n=n\,d_n+\sum_{t=1}^{n-1}(3t-2n)d_t s_{n-t}。$$

由于 $d_t$ 只有 $O(k^2)$ 个非零项，所以求每个 $s_n$ 时，求和只需要枚举这些非零项，单次复杂度是 $O(k^2)$。

---

如何从 $s_n$ 还原 $f_n$

由定义

$$S(x)=1-P(x)-2AF(x)$$

可知

$$s_n=-2Af_n-\,[x^n]P(x)。$$

如果 $n$ 不是特殊位置，那么 $[x^n]P(x)=0$，于是

$$s_n=-2Af_n。$$

如果 $n=s_i$ 是特殊位置，那么

$$[x^n]P(x)=(v_i-A)f_n。$$

总时间复杂度为 $O(nk^2)$。