P9536 [YsOI2023] Prüfer 序列

Ysuperman 模板测试的计数题。 众所周知，Prüfer 序列几乎没有在正赛中出现过，所以它需要出现在洛谷月赛中。

众所周知，一棵 $n$ 个点的有标号无根树与他的 Prüfer 序列一一对应。如果你不知道 Prüfer 序列指的是什么，可以参考下面提示说明中对 Prüfer 序列的解释。 现在给你一个长度为 $m$ 的正整数序列 $a$，其中 $a_i\in[1,n]$。等概率随机选择这个序列的一个长度为 $n-2$ 的子序列（只要选择下标不同就认为两个子序列不同）作为 Prüfer 序列构造得到一棵树 $T$，对于所有 $1\le i

输入第一行两个正整数 $n,m$。 第二行 $m$ 个整数表示序列 $a$，保证 $1\le a_i\le n$。

输出 $n-1$ 个非负整数，第 $i$ 个整数表示 $\mathrm{dist}(i,n)$ 的期望。

#### 对 Prüfer 序列的解释 对于一棵给定的无根有标号树，Prüfer 序列的构建过程如下：每次选择一个编号最小的叶结点并删掉它，然后在序列中记录下它连接到的那个结点，重复 $n-2$ 次后就只剩下两个结点，此时记录下来的那个序列就是这棵无根有标号树的 Prüfer 序列。 我们可以证明，一棵结点数量大于 $1$ 的无根有标号树和一个 Prüfer 序列是一一对应的，并且任意一个长度为 $n-2$ 每个数取 $[1,n]$ 范围内的整数的 Prüfer 序列都有唯一对应它的树，所以同样的，我们也可以根据一个 Prüfer 序列还原出一棵树。 有关 Prüfer 序列更加详细的内容，你可以参考 [OI wiki 上关于 Prüfer 序列的描述](https://oi-wiki.org/graph/prufer/)。 #### 样例 1 解释 共有三种等可能选择的子序列：$2,4$，$2,3$，$4,3$。 1. $2,4$ 对应的树为一条链 $1-2-4-3$，其中 $1,2,3$ 与 $4$ 的距离分别为 $2,1,1$。 2. $2,3$ 对应的树为一条链 $1-2-3-4$，其中 $1,2,3$ 与 $4$ 的距离分别为 $3,2,1$。 3. $4,3$ 对应的树为一条链 $1-4-3-2$，其中 $1,2,3$ 与 $4$ 的距离分别为 $1,2,1$。 所以 $\mathrm{dist}(1,4)$ 期望为 $(2+3+1)/3=2$，$\mathrm{dist}(2,4)$ 期望为 $(1+2+2)/3=5/3\equiv 666666673\pmod{10^9+7}$，$\mathrm{dist}(3,4)$ 期望为 $(1+1+1)/3=1$。 #### 样例 2 解释 仅有一种可能的子序列 $4,6,5,2$，对应的树为一条链 $1-4-5-2-6-3$，$1,2,3,4,5$ 与 $6$ 的距离依次为 $4,1,1,3,2$，即为答案。 #### 数据范围 本题共 $20$ 个测试点： |测试点编号|$n$|$m$| |:-:|:-:|:-:| |$1$|$=4$|$=6$| |$2$|$=8$|$=15$| |$3$|$=10$|$=20$| |$4$|$=10$|$=50$| |$5$|$=10$|$=200$| |$6$|$=10$|$=1000$| |$7$|$=10$|$=1750$| |$8$|$=10$|$=2500$| |$9$|$=11$|$=500$| |$10$|$=11$|$=1000$| |$11$|$=12$|$=250$| |$12$|$=12$|$=375$| |$13$|$=12$|$=400$| |$14$|$=13$|$=80$| |$15$|$=13$|$=120$| |$16$|$=13$|$=160$| |$17$|$=13$|$=200$| |$18$|$=14$|$=60$| |$19$|$=14$|$=90$| |$20$|$=15$|$=40$| 另外，对于所有数据，保证 $1\le a_i\le n$。 **请注意，前 $19$ 个测试点空间限制为 $512\rm{MB}$，最后一个点空间限制为 $150\rm{MB}$。**