生成函数大法好。
思路
考虑 prufer 序列。
如果 \(n\) 个点的度数确定，那么生成树个数为：
\[\frac{(n-2)!}{\prod (d_i-1)} \]那么在此题中，\(n\) 个点的度数确定，那么方案数为：
\[\frac{(n-2)!}{\prod (d_i-1)}\prod\frac{a_i!}{(a_i-d_i)!} \]其中，\(\sum d_i=2\times n-2\)。
容易发现这是一个卷积形式。
我们可以将每一个点的贡献拿出来，即 \(\frac{a_i!}{(a_i-d_i)!(d_i-1)}\)。
那么可以设生成函数：
\[f_i(x)=\sum_{j=1}\frac{a_i!x^j}{(a_i-j)!(j-1)} \]有：
\[\begin{align} f_i(x)&=\sum_{j=1}\frac{a_i!x^j}{(a_i-j)!(j-1)}\\ &=x\sum_{j=0}a_i!\frac{x^j}{(a_i-j+1)!j}\\ &=x\sum_{j=0}a_i\frac{x^j(a_i-1)!}{(a_i-j+1)!j}\\ &=x\sum_{j=0}a_ix^j\binom{a_i-1}{j}\\ &=a_ix\sum_{j=0}x^j\binom{a_i-1}{j}\\ &=a_ix(1+x)^{a_i-1} \end{align} \]我们要求的是：
\[\begin{align} (n-2)![x^{2\times n-2}]\prod_{i=1}^n a_ix(1+x)^{a_i-1} \end{align} \]这东西也可以推一下：
\[\begin{align} &=(n-2)![x^{2\times n-2}]\prod_{i=1}^n a_ix(1+x)^{a_i-1}\\ &=(n-2)![x^{n-2}]\prod_{i=1}^n a_i(1+x)^{a_i-1}\\ &=(n-2)!\prod_{i=1}^n a_i\times [x^{n-2}](1+x)^{\sum a_i-n}\\ &=(n-2)!\prod_{i=1}^n a_i\times \binom{\sum a_i-n}{n-2}\\ &=\prod_{i=1}^n a_i\times \prod_{i=0}^{n-3} (\sum a_i-n-i)\\ \end{align} \]时间复杂度：\(O(n)\)。
Code
#include <bits/stdc++.h>
using namespace std;
#define int long long
const int mod = 998244353;
int n, m, s;
int a[200010];
signed main() {
cin >> n, s = 1;
for (int i = 1; i <= n; i++) cin >> a[i];
for (int i = 1; i <= n; i++) (m += a[i]) %= mod;
for (int i = 1; i <= n; i++) (s *= a[i]) %= mod;
for (int i = 0; i <= n - 3; i++) (s *= (m - n - i)) %= mod;
cout << (s + mod) % mod << "\n";
}