自动搬运

查看原文

来自洛谷，原作者为

	OwenOwl ;

搬运于2025-08-24 21:55:26，当前版本为作者最后更新于2018-10-21 22:38:47，作者可能在搬运后再次修改，您可在原文处查看最新版

自动搬运只会搬运当前题目点赞数最高的题解，您可前往洛谷题解查看更多

以下是正文

---

我来胡一个 $O(n\log^2n)$ 做法。

考虑用 Prufer 序列去对应树，设 $d_i$ 表示 $i$ 在 Prufer 序列中出现的次数，则有 $\sum d_i = n - 2$。

考虑度数序列 $d$ 造成的贡献是：

$$\frac{(n-2)!}{\prod d_i!}\prod(d_i+1)^ma_i^{d_i+1}\sum (d_i+1)^m $$$$=(n-2)!\prod a_i \sum_j \frac{1}{\prod d_i!} \prod a_i^{d_i}\prod_{i\ne j}(d_i+1)^m (d_j+1)^{2m} $$

这前面的 $(n-2)!\prod a_i$ 是常数，只考虑后面的这个 $\sum$。

设后面这个 $\sum$ 关于 $\sum d_i$ 的生成函数是 $F(x)$。

我们看到每一个 $d_i$ 造成的贡献是 $\frac{1}{d_i!} a_i^{d_i}(d_i+1)^m$ 或者最后一个幂次是$2m$。

自然而然想到 $F(x)$ 会是很多关于 $a_ix$ 的多项式的积，即设：

$$A(x)=\sum_{k} \frac{1}{k!} (k+1)^m x^k$$ $$B(x)=\sum_{k} \frac{1}{k!} (k+1)^{2m} x^k$$

那么有：

$$F(x)=\sum_i B(a_ix) \prod_{j\ne i} A(a_j x)$$ $$=\sum_i \frac{B(a_i x)}{A(a_i x)} \prod_i A(a_ix)$$ $$=\sum_i \frac{B(a_i x)}{A(a_i x)} \cdot \exp {\sum_i \ln A(a_ix)} $$

求出 $\frac{B(x)}{A(x)}$ 和 $\ln A(x)$ 后，需要代入 $a_ix$ 并求和，即第 $t$ 项系数需要乘 $\sum a_i^t$

于是还要对 $0\le k < n-1$ 预处理一个 $\sum_i a_i^k$。

注意到$\sum_{k\ge 0}a^kx^k=\frac{1}{1-ax}$

则答案的生成函数为

$$\sum_{i=1}^n\frac{1}{1-a_ix}=\frac{\sum\limits_{i=1}^n\prod\limits_{j\neq i}(1-a_jx)}{\prod\limits_{i=1}^n(1-a_ix)} $$

其中，

$$Q(x)=\prod_{i=1}^n(1-a_ix)$$

可以用分治 FFT 求出。

对比分子和分母的系数（或是把分母反转，求导，再反转）得到：

$$P(x)=\sum_{i=1}^n\prod_{j\neq i}(1-a_jx)=\sum_{k=0}^{n-1}x^k(n-k)[x^k]Q(x) $$