题解：P12355 「HCOI-R2」巡回演出

· · 题解

由于点的编号不重要，故我们忽略给出的 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)。