方差（variance）

题目描述：

给定 $n$ ，求所有 $n$ 个点有标号无根树的度数的方差之和。对 $998244353$ 取模。

$n\le 10^6$ 。

根据 Prufer 序列，所有$n$ 个点有标号无根树与长度为 $n-2$ ，每一个元素范围 $[1,n]$ 的序列一一对应，且 $i$ 在序列中出现的次数为 $d_i-1$ 。

设方差为 $D$ ，平均值为 $p=\frac{2(n-1)}{n}$ ，则：

$$D=\frac{1}{n}\sum_{i=1}^n d_i^2-p^2$$

先看 $-p^2$ 这一项。由 Prufer 序列得共有 $n^{n-2}$ 种有标号无根树，故这一项的和为 $-n^{n-2}p^2$ 。

再看前面一项。由对称性，我们不妨只计算在所有的有标号无根树中 $d_1^2$ 的和，最后将答案 $\times n$ 即可。

我们枚举 $d_1$ 的值，并计算有多少种有标号无根树满足 $1$ 的度数为 $d_1$ ，则由 Prufer 序列，这一件事等价于一个长度 $n-2$ ，值域 $[1,n]$ 的序列中拥有恰好 $d_1-1$ 个 $1$ 。因此不妨钦定序列中 $d_1-1$ 个位置为 $1$ ，其余位置为 $[2,n]$ 中任意值，则有 $\binom{n-2}{d_1-1}(n-1)^{n-2-(d_1-1)}$ 中方案。

故前一项的和为：

$$\sum_{i=1}^{n-1} \binom{n-2}{i-1}(n-1)^{n-2-(i-1)}$$

然后就做完了。