自动搬运

查看原文

来自洛谷，原作者为

	bluedream **

搬运于2025-08-24 23:14:54，当前版本为作者最后更新于2025-04-30 20:37:18，作者可能在搬运后再次修改，您可在原文处查看最新版

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

以下是正文

---

由于点的编号不重要，故我们忽略给出的 DFS 序并固定根为结点 $1$，最终给答案乘 $n$ 即可。

对 $w_i$ 做前缀和，令 $d(i)$ 表示 $i$ 的度数，则一棵树的权值为 $\sum w_{d(i)}$。考虑求出所有 DFS 序的答案之和再除以 $n!$，这相当于求树的权值乘以其 DFS 序数量之和。使用 Prufer 序列，记 $c_i$ 为 $i$ 在 Prufer 序列中的出现次数，则所求为

$$\left(\sum_i w_{c_i+1}\right)(c_1+1)!\prod_{i\ne 1}c_i! $$

要求 $\sum c_i=n-2$，不妨使用生成函数工具，注意一棵树的权值为每个结点贡献之和而非乘积，写出答案的 EGF：

$$\left[\dfrac{x^{n-2}y^1}{(n-2)!}\right]\left(\sum_i(w_{i+1}y+1)x^i\right)^{n-1}\left(\sum_i(w_{i+1}y+1)(i+1)x^i\right) $$

那么只需简单讨论一下 $y$ 在哪一侧取到，若其在右侧取到则贡献为：

$$\sum_{i}w_{i+1}(i+1)\binom{2n-i-4}{n-2}$$

否则在左侧取到，贡献为：

$$(n-1)\sum_{i}w_{i+1}\sum_j(j+1)\binom{2n-i-j-5}{n-3} $$$$(n-1)\sum_{i}\binom{2n-i-5}{n-3}\sum_{j=0}^iw_{j+1}(i-j+1) $$

时间复杂度 $O(\sum n)$。