{"problem":{"name":"[YsOI2023] Prüfer 序列","description":{"content":"众所周知，一棵 $n$ 个点的有标号无根树与他的 Prüfer 序列一一对应。如果你不知道 Prüfer 序列指的是什么，可以参考下面提示说明中对 Prüfer 序列的解释。 现在给你一个长度为 $m$ 的正整数序列 $a$，其中 $a_i\\in[1,n]$。等概率随机选择这个序列的一个长度为 $n-2$ 的子序列（只要选择下标不同就认为两个子序列不同）作为 Prüfer 序列构造得到一棵树 $","description_type":"Markdown"},"platform":"Luogu","limit":{"time_limit":2000,"memory_limit":524288},"difficulty":{"LuoguStyle":"P7"},"is_remote":true,"is_sync":true,"sync_url":null,"sign":"LGP9536"},"statements":[{"statement_type":"Markdown","content":"众所周知，一棵 $n$ 个点的有标号无根树与他的 Prüfer 序列一一对应。如果你不知道 Prüfer 序列指的是什么，可以参考下面提示说明中对 Prüfer 序列的解释。\n\n现在给你一个长度为 $m$ 的正整数序列 $a$，其中 $a_i\\in[1,n]$。等概率随机选择这个序列的一个长度为 $n-2$ 的子序列（只要选择下标不同就认为两个子序列不同）作为 Prüfer 序列构造得到一棵树 $T$，对于所有 $1\\le i<n$，你需要求出 $\\mathrm{dist}(i,n)$ 的期望（$\\mathrm{dist}(u,v)$ 定义为 $u,v$ 两点简单路径的边数）。\n\n答案对 $10^9+7$ 取模。\n\n## Input\n\n输入第一行两个正整数 $n,m$。\n\n第二行 $m$ 个整数表示序列 $a$，保证 $1\\le a_i\\le n$。\n\n## Output\n\n输出 $n-1$ 个非负整数，第 $i$ 个整数表示 $\\mathrm{dist}(i,n)$ 的期望。\n\n[samples]\n\n## Background\n\nYsuperman 模板测试的计数题。\n\n众所周知，Prüfer 序列几乎没有在正赛中出现过，所以它需要出现在洛谷月赛中。\n\n## Note\n\n#### 对 Prüfer 序列的解释\n\n对于一棵给定的无根有标号树，Prüfer 序列的构建过程如下：每次选择一个编号最小的叶结点并删掉它，然后在序列中记录下它连接到的那个结点，重复 $n-2$ 次后就只剩下两个结点，此时记录下来的那个序列就是这棵无根有标号树的 Prüfer 序列。\n\n我们可以证明，一棵结点数量大于 $1$ 的无根有标号树和一个 Prüfer 序列是一一对应的，并且任意一个长度为 $n-2$ 每个数取 $[1,n]$ 范围内的整数的 Prüfer 序列都有唯一对应它的树，所以同样的，我们也可以根据一个 Prüfer 序列还原出一棵树。\n\n有关 Prüfer 序列更加详细的内容，你可以参考 [OI wiki 上关于 Prüfer 序列的描述](https://oi-wiki.org/graph/prufer/)。\n\n#### 样例 1 解释\n\n共有三种等可能选择的子序列：$2,4$，$2,3$，$4,3$。\n\n1. $2,4$ 对应的树为一条链 $1-2-4-3$，其中 $1,2,3$ 与 $4$ 的距离分别为 $2,1,1$。\n2. $2,3$ 对应的树为一条链 $1-2-3-4$，其中 $1,2,3$ 与 $4$ 的距离分别为 $3,2,1$。\n3. $4,3$ 对应的树为一条链 $1-4-3-2$，其中 $1,2,3$ 与 $4$ 的距离分别为 $1,2,1$。\n\n所以 $\\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$。\n\n#### 样例 2 解释\n\n仅有一种可能的子序列 $4,6,5,2$，对应的树为一条链 $1-4-5-2-6-3$，$1,2,3,4,5$ 与 $6$ 的距离依次为 $4,1,1,3,2$，即为答案。\n\n#### 数据范围\n\n本题共 $20$ 个测试点：\n\n|测试点编号|$n$|$m$|\n|:-:|:-:|:-:|\n|$1$|$=4$|$=6$|\n|$2$|$=8$|$=15$|\n|$3$|$=10$|$=20$|\n|$4$|$=10$|$=50$|\n|$5$|$=10$|$=200$|\n|$6$|$=10$|$=1000$|\n|$7$|$=10$|$=1750$|\n|$8$|$=10$|$=2500$|\n|$9$|$=11$|$=500$|\n|$10$|$=11$|$=1000$|\n|$11$|$=12$|$=250$|\n|$12$|$=12$|$=375$|\n|$13$|$=12$|$=400$|\n|$14$|$=13$|$=80$|\n|$15$|$=13$|$=120$|\n|$16$|$=13$|$=160$|\n|$17$|$=13$|$=200$|\n|$18$|$=14$|$=60$|\n|$19$|$=14$|$=90$|\n|$20$|$=15$|$=40$|\n\n另外，对于所有数据，保证 $1\\le a_i\\le n$。\n\n**请注意，前 $19$ 个测试点空间限制为 $512\\rm{MB}$，最后一个点空间限制为 $150\\rm{MB}$。**","is_translate":false,"language":"English"}],"meta":{"iden":"LGP9536","tags":["动态规划 DP","洛谷原创","O2优化","洛谷月赛"],"sample_group":[["4 3\n2 4 3\n","2 666666673 1"],["6 4\n4 6 5 2","4 1 1 3 2"],["10 12\n6 9 2 10 1 5 5 9 10 7 8 3\n","585858594 60606064 8080810 834343444 638383846 785858595 913131322 595959602 286868692"]],"created_at":"2026-03-03 11:09:25"}}